  Close Menu Navigation

More Sequences

Find a closed form formula for the recurrence relation 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.

Show that  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 . Woosh