Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

  • Index
  •  » Help Me !
  •  » Help understanding equation- recurrence relation

Post a reply

Go back

Write your message and submit
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool: | :dizzy :eek :kiss :roflol :rolleyes :shame :down :up :touched :sleep :wave :swear :tongue :what :faint :dunno
Options

Go back

Topic review (newest first)

Robin
2005-08-07 01:03:40

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

MathsIsFun
2005-08-06 15:50:17

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 !

Robin
2005-08-06 10:44:43

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

MathsIsFun
2005-08-06 09:37:49

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"

Robin
2005-08-05 22:38:32

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

Robin
2005-08-05 22:00:16

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

Board footer

Powered by FluxBB