So I have a bonus question on a homework assignment I am working on that literally just asks "How would you prove a recursive formula by induction?" There are no numbers, or sequences given.
I understand how to prove something using induction, but am very confused on how to go about doing it for a recursive formula.
Any ideas?
On
An example. The Fibonacci numbers. $F(0)=0.\;$ $\;F(1)=1.$ Recursively, $F(n+2)=F(n+1)+F(n).$ Prove, by induction, the formula $$F(n)=(a^n-b^n)/\sqrt 5,$$ where $a=(1+\sqrt 5)/2\;$ and $\;b=(1-\sqrt 5)/2.$
Note that $a$ and $b$ are the solutions to $x^2=x+1.$ So $a^2=a+1 $ and $b^2=b+1.$
So if the formula is valid for $n$ and for $n+1$ then $$(a^{n+2}-b^{n+2})/\sqrt 5=[a^n(a^2)-b^n(b^2)]/\sqrt 5=$$ $$=[a^n(a+1)-b^n(b+1)]/\sqrt 5=$$ $$=[a^{n+1}-b^{n+1}]/\sqrt 5\; +\; [a^n-b^n]/\sqrt 5=$$ $$=F(n+1)+F(n)=F(n+2).$$ Then confirm that the formula is valid for $n=0$ and for $n=1.$
Your mission, if you choose to accept it, is to outline the steps involved in proving by induction that $\forall k\geq 0:a_k = g(k)$ when given that $a_0=c$ and $\forall k\geq 0:a_{k+1} = f(a_{k})$.
That is how do you prove $a_k=g(k)$ is the closed form of the recursion formula.
As you understand what proof by induction involves, what is the first thing you would do?
That's the exactly right thing to do. So, do that then.
Okay, what is the base case here?
Yes, and what are you assuming is true for any $k$ here?
Likewise what do you need to prove for $k+1$.
It should not be that confusing. It is just a matter of identifying how to use the recursion formula to move from the assumption to the required conclusion.