# 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