You are not logged in.
#1 2005-08-05 22:00:16
- Robin
- Guest
Help understanding equation- recurrence relation
Hi all,
I have a simple sum I.e x=a*b+c =20 * 2 + 2 = 42.
If I want to continue the process and repeat the sum using the number generated previously
as in 42*2+2=86 and repeat again using 86 as the start.
The multiplying and addition figures will allways be the same and only the first digit will change.
This I have found out is called recurrence relations, but I cant seem to get my head around, where to start to actually write this as a formula.
A friend suggested the following, but I still dont get it (Blush)
to S_n+1= S_0+(2^n-1)*(S_1-S-0) ==> S_n+1= 20+(2^n-1)*22.
Can anyone break it down, so an idiot like me can understand it... I mean really simple please.
In my world if I start with 20 and di the first few iterations I get the following
20*2+2=42
42*2+2=86
86*2+2=174
etc
Thanks
Robin
#2 2005-08-05 22:38:32
- Robin
- Guest
Re: Help understanding equation- recurrence relation
Hi again,
Sorry, but came to answer my on problem. Please correct me if you see something wrong.
I've broken the equation down that my friend suggested, and believe it to be correct...well, it gives the right answers.
S_n = 2*S_n-1 + 2
= 2*2*S_n-2 + 4 + 2
= 2*2*2*S_n-3 + 8 + 4 + 2
= 2*2*2*2*S_n-4 + 16 + 8 + 4 + 2
= 2^n*S_0 + (2*2^n-2)
= 2^n*(20+2)-2
= 2^n*22-2
Thanks again. nice site.
Robin
#3 2005-08-06 09:37:49
- MathsIsFun
- Administrator
Offline
Re: Help understanding equation- recurrence relation
You could even make it more general,
If each time you multiply the previous answer by "a", then add "b" you would have:
S_n = a * S_n-1 + b
= a ( a * S_n-2 + b ) + b = a^2 * S_n-2 + ab + b
= a ( a^2 * S_n-3 + ab + b ) + b = a^3 * S_n-3 + a^2b + ab + b
= ...
= a^n*S_0 + b(a^(n-1) + a^(n-2) + ... + a^0)
In your case (a=2), the expansion of "a^(n-1) + a^(n-2) + ... + a^0" is just "2^n-1"
"The physicists defer only to mathematicians, and the mathematicians defer only to God ..." - Leon M. Lederman
#4 2005-08-06 10:44:43
- Robin
- Guest
Re: Help understanding equation- recurrence relation
I hate to say it, but I cant seem to repeat the process with different no.s
I could follow the idea my friend gave me and break it down, but when I try to apply the same ideas against
X * 9 + 4 I keep on failing.
I just don't understand how you go about starting to write such a function. I've tried reading a few sites on recurring patterns, but they all seem gobbly gook to me at the moment....It is 2:40 am here though !
Would someone mind helping me out. I really would appreciate a desription, step by step on how to complete it.
I need to be able to formulate it so that I can write a function for it.
Thanks
Robin
#5 2005-08-06 15:50:17
- MathsIsFun
- Administrator
Offline
Re: Help understanding equation- recurrence relation
You got lucky with a=2, because the expansion of "a^(n-1) + a^(n-2) + ... + a^0" is just "2^n-1" for a=2
A general formula for "a^(n-1) + a^(n-2) + ... + a^0" is: (a^n-1)/(a-1)
For example 3^4+3^3+3^2+3^1+3^0 = 81+27+9+3+1 = 121
Can be simplified using (a^n-1)/(a-1): (3^5-1) / (3-1) = (243-1)/(3-1) = 121
So, try:
S_n = a^n*S_0 + b( (a^n-1)/(a-1) )
Let us try a start value of S_0 = 20, and have a=3 and b=4
S_0 = 20
S_1 = 20*3+4=64
S_2 = 64*3+4=196
S_3 = 196*3+4=592
Let's check S_3 (n=3) using our new formula:
S_3 = 3^3 * 20 + 4 * (3^3 -1)/(3-1)
= 27*20 + 4 * 26/2
= 592
Well, that worked, let's hope others work ... over to you for checking !
"The physicists defer only to mathematicians, and the mathematicians defer only to God ..." - Leon M. Lederman
#6 2005-08-07 01:03:40
- Robin
- Guest
Re: Help understanding equation- recurrence relation
Hi again.
Thanks for your reply. I've had my morning coffee and have tried again
Let us try a start value of S_0 = 13, and have a=9 and b=4
S_n = a^n*S_0 + b( (a^n-1)/(a-1) )
s_0 = 13
s1 = 13*9+4=121
s2 = 121*9+4=1093
s3 = 1093*9+4=9841
checkin S_3 (n=3) using our new formula:
s3 = 9^3 * 13 + 4 * ( 9^3-1) / (9-1)
= 729 * 13 + 4 * 728 / 8
= 9841
After a few attempts..missunderstandings.. I've finally absorbed it. Thanks for all your help. I wouldn't of been able to figure it without it.
Regards
Robin