Solution by Iteration: Nonrecursive Formula for a_n = 2(n+1)^n

[Goldenwind]

[SOLVED] Recurrence Relations

Homework Statement

I need to express this recursive statement as a nonrecursive formula, using the technique of itteration.

$$a_n = (n+1)a_{n-1}$$
$$a_0 = 2$$

The Attempt at a Solution

$$a_n = (n+1)a_{n-1}$$
$$a_n = (n+1)(n+1)a_{n-2} = (n+1)^{2}a_{n-2}$$
$$a_n = (n+1)(n+1)(n+1)a_{n-3} = (n+1)^{3}a_{n-3}$$
$$a_n = (n+1)^{n}a_{n-n}$$
$$a_n = 2(n+1)^{n}$$

I plugged both the recursive formula, and my answer, into MS-Excel, and they don't match up. They work for n = 0,1, but then my answer start getting larger than the recursive one.

 

[Goldenwind]

Here's the spreadsheet I'm using to check my answer.

First column is n
Second column is the recursive
Third column is my proposed answer

 

[tiny-tim]

$$a_n = (n+1)a_{n-1}$$
$$a_0 = 2$$

Hi Goldenwind!

With these recurrence questions, always start by working out what a_n+2 is in terms of a_n.

Then a_n+3.

By then, you should have a good idea of what is happening.

So … what is happening?

 

[Goldenwind]

$$a_n = (n+1)a_{n-1}$$

Which is the same as
$$\frac{a_{n+1}}{n+1} = a_{n}$$$$\frac{a_{n+2}}{{(n+1)}^2} = a_{n}$$$$\frac{a_{n+3}}{{(n+1)}^3} = a_{n}$$

I still don't see my mistake :(
This is pretty much what I did above, only the other way around >.>

 

[tiny-tim]

$$a_n = (n+1)a_{n-1}$$

Which is the same as
$$\frac{a_{n+1}}{n+1} = a_{n}$$


$$\frac{a_{n+2}}{{(n+1)}^2} = a_{n}$$


$$\frac{a_{n+3}}{{(n+1)}^3} = a_{n}$$

No no no …

First, don't rearrange the formula - it's simplest as it is!

Then … be careful!

You should have $$a_{n+2}\,=\,(n+2)a_{n+1}\,=\,(n+2)(n+1)a_n\,.$$

So … the nonrecursive formula is … ?

 

[HallsofIvy]

I always start a problem involving any kind of sequence by working out a few values!

$a_1= (1+1)a_0= 2a_0$
$a_2= (2+1)a_1= 3a_1= 3(2)a_0$
$a_3= (3+1)a_2= 4a_2= 4(3)(2)a_0$
$a_4= (4+1)a_3= 5a_3= 5(4)(3)(2)a_0$

Anything come to mind?

 

[Goldenwind]

$a_n = 2(n+1)!$
...is what it looks like to me.

However, even if I know the formula, I need to demonstrate that this *is* the formula, via iteration.

As in, I start out with $a_n = (n+1)a_{n-1}$, then replace $a_{n-1}$ with $a_{n-1} = (n+1)a_{n-2}$, then replace $a_{n-2}$ with $a_{n-2} = (n+1)a_{n-3}$, and so on, until I get to $a_{n-n} = a_0$, where I can simply sub in the given base value, as shown above.

 

[Goldenwind]

Yeah, I see my mistake... when I replaced n with n-1, or n-1 with n-2, I didn't change the (n+1) at all. Doing so would lead to the factorial, instead of $(n+1)^n$.

Thank you for your help :)