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 :)