Find a closed form formula for the recurrence relation
Table Of Content
1. Let’s guess at an answer
Let’s look at the expansion of the recurrence
the following table will give the values of
Once again, we see that the boxed indexes display the property that . Hence, for even values of , the equation holds. We now use this to guess that in general
2. Show that
We can prove this inductively on values of even . Informally, we will use for even to show that our proposition holds for even values of , and then use those even values to confirm that the proposition holds for odd as well.
Show that for even values of
We need to prove the proposition is true for even values of .
As our starting point, it is obvious that holds. We now outline the induction steps.
This concludes our proof that for even values of
Show that for odd values of
Because odd, this becomes equivalent to showing . For odd values of , we’ve already shown , hence we only need to show
This concludes our proof that for odd values of
Because for both even and odd values of , then naturally, for all natural values of .