Strong Induction and Recursion

Question

Consider the recursion given by \begin{equation}f(n) = 2f(n−1)− f(n−2)+6 \text{ for } n ≥ 2 \text{ with } f (0) = 2 \text{ and }f (1) = 4 \end{equation} Use mathematical induction to prove that \begin{equation}f (n) = 3n^2 −n+2 \text{ for all integers } n ≥ 0 \end{equation}

I don't see how I can use induction to prove this problem.

Answer 1

HINT:

Let $f(n)=3n^2-n+2$ holds true for $0\le n\le m-1$

So, using Complete/Strong induction

$f(m)=2f(m-1)-f(m-2)+6=\cdots$

Answer 2

The base cases $n=0,1$ hold since $f(0)=2=3\cdot0^2-0+2$ and $f(1)=4=3\cdot 1^2-1+2$.

Now, suppose inductively that $f(k)=3k^2-k+2$ for $k\leq n$. Then $$ f(n+1) = 2f(n)-f(n-1)+6 $$ You can now apply the induction hypothesis to obtain the result.

Answer 3

To find the result without induction:

$$f(n) = 2f(n−1)− f(n−2)+6\iff f(n)-f(n-1)=f(n-1)-f(n-2)+6$$ so $$\sum_{k=2}^nf(k)-f(k-1)=f(n)-f(1)=\sum_{k=2}^n f(k-1)-f(k-2)+6\\=f(n-1)-f(0)+6(n-1)$$ so $$f(n)-f(n-1)=2+6(n-1)$$ hence $$\sum_{k=1}^nf(k)-f(k-1)=f(n)-f(0)=\sum_{k=1}^n2+6(k-1)=2n+3(n-1)n$$ and finaly we have $$f(n)=3n^2-n+2$$