# Figuring out the steps in a Recursive Function

I have the following recursive function:

$f(0) = 7$

$f(n+1) = f(n) + 6n + 1$ for all integers $n => 0$

I know the answer is $f(n) = 3n^2 + 2n + 7$ I would like to know the steps to get to this result.

-
f(n) should be 3n^2 - 2n + 7 because f(1) = 8 but your f(1) = 12. – DeepSea Feb 27 '14 at 3:38

We have $f(n+1)=f(n)+6n+1\Rightarrow f(n+1)-f(n)=6n+1$. From that we can have $$f(1)-f(0)=6.0+1\\ f(2)-f(1)=6.1+1\\ f(3)-f(2)=6.2+1\\ ---------\\ ---------\\ ---------\\ f(n)-f(n-1)=6.(n-1)+1$$ Adding all them up together we have $$f(n)-f(0)=6\{0+1+2+........+(n-1)\}+n.1\\ f(n)-f(0)=6\frac{(n-1)(n-1+1)}{2}+n\\ f(n)=f(0)+6\frac{(n-1)n}{2}+n\\ f(n)=7+3n^2-3n+n\\ f(n)=3n^2-2n+7$$

-

Write

$f(n) = f(n) - f(n-1) + f(n-1) - f(n-2) + ... + f(1) - f(0) + f(0)$ $= 6(n-1) + 1 + + 6(n -2) + 1 + ... + 6*0 + 1 + 7$

$= 6*(n-1)*n/2 + n + 7$

$= 3n(n - 1) + n + 7$

$= 3n^2 - 2n + 7$

-

\begin{align} f(n)&= f(n-1)+6(n-1)+1\\ &=f(n-2)+6(n-2)+1+6(n-1)+1\\ &=f(n-2)+6(2n-2-1)+2\\ &=f(n-3)+6(n-3)+1+6(2n-2-1)+2\\ &=f(n-3)+6(3n-3-2-1)\\ &=\vdots\\ &=f(0)+6(n\cdot n-\Sigma_{i=1}^ni)+n\\ &=7+6(n^2-\frac{n(n+1)}{2})+n\\ &=3n^2-2n+7 \end{align}

-