• Support PF! Buy your school textbooks, materials and every day products Here!

Recurrence Relations

  • Thread starter Goldenwind
  • Start date
146
0
[SOLVED] Recurrence Relations

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

[tex]a_n = (n+1)a_{n-1}[/tex]
[tex]a_0 = 2[/tex]

3. The Attempt at a Solution
[tex]a_n = (n+1)a_{n-1}[/tex]
[tex]a_n = (n+1)(n+1)a_{n-2} = (n+1)^{2}a_{n-2}[/tex]
[tex]a_n = (n+1)(n+1)(n+1)a_{n-3} = (n+1)^{3}a_{n-3}[/tex]
[tex]a_n = (n+1)^{n}a_{n-n}[/tex]
[tex]a_n = 2(n+1)^{n}[/tex]

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.
 

Answers and Replies

146
0
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
 

Attachments

tiny-tim
Science Advisor
Homework Helper
25,789
249
[tex]a_n = (n+1)a_{n-1}[/tex]
[tex]a_0 = 2[/tex]
Hi Goldenwind! :smile:

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? :smile:
 
146
0
[tex]a_n = (n+1)a_{n-1}[/tex]

Which is the same as
[tex]\frac{a_{n+1}}{n+1} = a_{n}[/tex]


[tex]\frac{a_{n+2}}{{(n+1)}^2} = a_{n}[/tex]


[tex]\frac{a_{n+3}}{{(n+1)}^3} = a_{n}[/tex]

I still don't see my mistake :(
This is pretty much what I did above, only the other way around >.>
 
tiny-tim
Science Advisor
Homework Helper
25,789
249
[tex]a_n = (n+1)a_{n-1}[/tex]

Which is the same as
[tex]\frac{a_{n+1}}{n+1} = a_{n}[/tex]


[tex]\frac{a_{n+2}}{{(n+1)}^2} = a_{n}[/tex]


[tex]\frac{a_{n+3}}{{(n+1)}^3} = a_{n}[/tex]
No no no … :frown:

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

Then … be careful!

You should have [tex]a_{n+2}\,=\,(n+2)a_{n+1}\,=\,(n+2)(n+1)a_n\,.[/tex]

So … the nonrecursive formula is … ? :smile:
 
HallsofIvy
Science Advisor
Homework Helper
41,738
897
I always start a problem involving any kind of sequence by working out a few values!

[itex]a_1= (1+1)a_0= 2a_0[/itex]
[itex]a_2= (2+1)a_1= 3a_1= 3(2)a_0[/itex]
[itex]a_3= (3+1)a_2= 4a_2= 4(3)(2)a_0[/itex]
[itex]a_4= (4+1)a_3= 5a_3= 5(4)(3)(2)a_0[/itex]

Anything come to mind?
 
146
0
[itex]a_n = 2(n+1)![/itex]
...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 [itex]a_n = (n+1)a_{n-1}[/itex], then replace [itex]a_{n-1}[/itex] with [itex]a_{n-1} = (n+1)a_{n-2}[/itex], then replace [itex]a_{n-2}[/itex] with [itex]a_{n-2} = (n+1)a_{n-3}[/itex], and so on, until I get to [itex]a_{n-n} = a_0[/itex], where I can simply sub in the given base value, as shown above.
 
146
0
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 [itex](n+1)^n[/itex].

Thank you for your help :)
 

Related Threads for: Recurrence Relations

  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
0
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
0
Views
1K
Top