Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2005-08-05 00: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 00: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-05 11:37:49

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,552

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

Offline

#4 2005-08-05 12: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-05 17:50:17

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,552

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

Offline

#6 2005-08-06 03: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

Board footer

Powered by FluxBB