How to find the function that is computed from a recursive algorithm?

Question

The following is a recursive algorithm :

Procedure unknown(n belongs to N) 
  If n=0 then return 0
else return unknown (n-1)+5

The function that is computed from the algorithm is f(n) = 5*n. I want to know how it was computed.

Answer 1

You have $f(n)=f(n-1)+5,$ therefore $f(n)-f(n-1)=5\,$ is constant. So $f\,$ is affine, i.e. $f(n)=an+b.\,$ From $f(0)=0\,$ you get $b=0\,$ and from $f(n)-f(n-1)=5\,$ you find $a=5.$