Formula for (iterative?) series?

[da_silvy]

I was wondering what the rule for the following series would be and how to prove / solve it.

5, 12, 26, 54

i.e.

rule => t_n = 2t_n-1 + 2

How can I find an equation to get the value of the nth term?

[opus]

Try this:

n-Term = 2^(n-1)+ Sum [from n=2 to n] ( 2^n-1)

Sorry, but I don't know how to do the Sum-Symbol

[da_silvy]

what do u mean?

[from n=2 to n]

?

[opus]

Sum [from n=2 to n] ( 2^n-1)
should be to sum of:

2^1 +2^2 +...2^n

[opus]

just saw a mistake in my formula, forgot to put the term 5 in there!
n-Term = 2^(n-1)*5 + Sum [from n=2 to n] ( 2^n-1)

[da_silvy]

Perhaps i'm too stupid tonight

Can you show me how it works, with a value of n

say 4?

[opus]

n-Term = 2^(n-1)*5 + Sum [from n=2 to n] ( 2^n-1)

n=4

2^(4-1)*5 +Sum [from n=2 to 4] ( 2^n-1)

2^3*5 + 2^1 + 2^2 +2^3

8*5 + 2 +4+ 8

54

I saw it, I shouldn't have used n two times for different values!
Sorry for that
so let'S put it like:
n-Term = 2^(n-1)*5 + Sum [from a=2 to n] ( 2^a-1)

[sql_lall]

Ok, i do know how to solve this recurrence, but my notes are at school.

For now, i'll solve a slightly different one, but when i get my notes i'll

Recurrence: t_n = 2t_n-1 + 2t_n-2
Let t_n = xⁿ
=> x² = 2x + 2
=> x² - 2x - 2 = 0
there are two root to this r and s (= 1 +/- sqrt(3))
Now, the solution is in the form t_n = Arⁿ+Bsⁿ

As you have t₀ = 5
t₁ = 12
=> A+B=5, A (1+sqrt(3)) + B(1-sqrt(3) = 12
=> A,B solved simultaneously, and t_n = Arⁿ+Bsⁿ can be written out.

However, i know that the question you gave has just +2 at the end, i'll check to see what you do about that.

[NotLKH]

Seems to me the Kth term of the series 5, 12, 26, 54, ...
is 5 + (2^k-1)*7, but I just woke up and I could have made a mistake.

-Lou

[opus]

Sounds good to me, and it's more easily computed!

[NotLKH]

Originally posted by da_silvy
... how to prove ... it.

5, 12, 26, 54

i.e.

rule => t_n = 2t_n-1 + 2

I'll leave that up to you, but all you have to do {I think} is show,

if the t'th term = 5 + 7*(2^t - 1),
and the t+1 term = 2*(t'th term) + 2,

show that 5 + 7*(2^t+1 - 1) = 2*(5 + 7*(2^t - 1))+2

[NotLKH]

Think any one can prove the Following:

Problem #1
if X_i+1 = 2*X_i + B

and, given X₀

then

X_i = X₀ + (X₀ + B)*(2ⁱ - 1)

Problem #2
if X_i+1 = M*X_i + B

and, given X₀

then develop the generic equation for X_i, and prove it's valid.

To be honest, I've developed the generic equation for #2, but At this moment, I'm still thinking about the approach to take to "Prove" it in the simplest maner.

[sql_lall]

It is possible to solve these recurrences. I know i said i'd post a general solution, (like i have done when there's no constant at the end) but i keep forgetting to get the sheet soory
Anyway, if i have a good enough memory, i'll try posting it tomorrow.

[sql_lall]

t_n+1=2t_n+2

Step 1: Assume there is no "+2"

Step 2: Wite with xⁿ=t_n...
=> x - 2 = 0; x = 2
=> t_n=K * 2ⁿ --(**eq. 1**)

Step 3: "Guess" that t_n = c (c=constant)
=> c = 2c + 2; c = -2
=> t_n = -2 --(**eq. 2**)

Step 4: combine equations 1 & 2:
=> t_n = K * 2ⁿ - 2

Step 5: find unknown K:
t₀ = K-2 = 5
=> K = 7
=> t_n = 7 * 2ⁿ - 2

(N.B. this is assuming t₀ = 5. If you wanted to say t₁= 5, this is just as easy)

You can use this method to devise a general formula, which i'll do tonight if no-one else has posted it.

BTW, sorry about the "guess" part, there is a more formal way to do it, but the best word to describe this formal way is still "guess"

[sql_lall]

Last period on a friday, have a I free, so i have nothing better to do. Here's the general formula:

A * t_n+1 = B * t_n + C
t₀ = P

Solution: (from step detail, see above)
Step 1&2: t_n = K * (B/A)ⁿ
Step 3: t_n = C/(A-B)
Step 4: t_n = K * (B/A)ⁿ + C/(A-B)
Step 5: K = P - C/(A=B)

=> General fomula:
t_n = (P - C/(A-B)) * (B/A)ⁿ + C/(A-B)

TADA!!!

Checking with the given formula:
A = 1; B = 2; C = 2; P = 5

=> t_n = (5 - 2/(1-2)) * (2/1)ⁿ + 2/(1-2)
=> t_n = (5 - 2/(-1)) * (2)ⁿ + 2/(-1)
=> t_n = 7 * (2)ⁿ - 2...look familiar

Also, my 222nd post

[NotLKH]

Originally posted by sql_lall
Last period on a friday, have a I free, so i have nothing better to do. Here's the general formula:

A * t_n+1 = B * t_n + C
t₀ = P

....
=> General fomula:
t_n = (P - C/(A-B)) * (B/A)ⁿ + C/(A-B)

TADA!!!

Very Nice!


It agrees with what I developed nicely.

Here's My formula.

[NotLKH]

Ok, How about this challange:

Given X₀ and X₁, what is the generic equation for X_i, when:

X_i+2 = m*X_i+1 + n*X_i + b

[NotLKH]

Originally posted by NotLKH
Ok, How about this challange:

Given X₀ and X₁, what is the generic equation for X_i, when:

X_i+2 = m*X_i+1 + n*X_i + b

Hmm,
Looks like X_i can be seperated into two independent series, X_even and X_odd...

ie...

X_i+2 = m*X_i+1 + n*X_i + b

can be considered identical to

When i is even,

X_i+2 = k*X_i + B1

and when i is odd,

X_i+2 = j*X_i + B2

now, how do i .... hmmmm.

[NotLKH]

hmmm,

I'm puzzled.

Lets say I have:

X₀ = 1, X₁ = 2, and:

X_i+2 = X_i+1 + 2*X_i + 3

This forms the series:
1, 2, 7, 14, 31, 62, ...

So,

When i is even,
X_i = 1 + 2*(4^(i/2)-1)

and when i is odd,
X_i = 2 + 4*(4^((i-1)/2)-1)

But, what is X_i when i <> integer, ie, perhaps when i = 1.6?

[NotLKH]

hmmmm

How about these:

hmmm #1
If X_i+1 = a*X_i² + b*X_i + c,

and Given X₀

What is the generic formula for X_i?

hmmm #2
If X_i+1 = (0.2)*X_i² - (0.4)*X_i - 1,

What is the Range of X₀ such that X_i+1 does NOT approach infinity, as i -> infinity?

hmmm #3
Within that range of X₀ from hmmm #2, does X_i+1 approach a single value as i -> infinity?

if so, what is it?

[sql_lall]

Yeah, i know how to do it. Really just what i have been talking about before.

A*X_i+2 = B*X_i+1 + C*X_i + D

I.e. split into
A*X_i+2 = B*X_i+1 + C*X_i
and
A*X_i+2 = D

Solve #1 by writing X_i = nⁱ
Solve #2 by writing X_i = c
Combine the two

I'll do this, and reply tomorrow. However someone can beat me to it if they wish

[NotLKH]

Originally posted by NotLKH
hmmm,

I'm puzzled.

Lets say I have:


This forms the series:
1, 2, 7, 14, 31, 62, ...

So,



But, what is X_i when i <> integer, ie, perhaps when i = 1.6?

Ok. Now I'm getting somewhere.

X_i = 2⁽ⁱ⁺¹⁾ - (1/2)*(3-(-1)ⁱ) for all i.

cool!

[bugzpodder]

sql_lall, can i challenge you something? find the formula for the following recurrence relation:

t_(n+2)=4t_(n+1)-4t_n

[NotLKH]

Originally posted by bugzpodder
sql_lall, can i challenge you something? find the formula for the following recurrence relation:

t_(n+2)=4t_(n+1)-4t_n

bugz,

do you know the anser{pardon, a few newcastle does NOT help your spelling!!!}, can any of us respond, or is this only for sql???



-Lou

[bugzpodder]

i can easily work out the answer. and sure anyone can respond, but this is mainly to show sql_lall that in this special case his formula does not work (some modifications are needed at length).

[sql_lall]

I know, repeated roots when using t_n=xⁿ
I was just a simple way to get it working for most cases. (In fact, I had only put up a general solution when using 2 t terms, not 3)

BTW, you need t₀ and t₁, unless of course you wanted them in the solution.

However, for most (i think) cases:
A*t_n+2=B*t_n+1 + C*t_n +D
t₀ = P, t₁ = Q.

Let R = (B+sqrt(B^2 + 4AC))/2A
Let S = (B-sqrt(B^2 + 4AC))/2A

Let (X,Y) be the numbers satisfying:
1) X + Y = P - D/(A-B-C)
2) RX + SY = Q - D/(A-B-C)
**special cases apply when R=S**
Also, this means X and Y can be written out in terms of A,B,C,D,P and Q, but it takes a fair bit of space, and would look messy.

=> the solution (in many cases) is:
t_n = X*Rⁿ + Y*Sⁿ + D/(A-B-C)

I've forgotten half of this stuff, but will check up the repeated roots thing tomorrow. (BTW, 'repeated roots' because when you use t_n = xⁿ, you get a quadratic with equal roots) I know there is something you can do, just forgotten what.

[bugzpodder]

I dont agree with D/(A+B+C) it just dont look right. we can have A=1 and D=1 and we are guarenteed to have integers, but D/(A+B+C) is definately not an integer

[sql_lall]

bugz:
Say you have a repeated root when using t_n=xⁿ then you write it a bit differently. To solve your example:
t_n+2=4t_n+1 - 4t_n
=> x²-4x+4=0
=> two factors of (x-2)
=> Write this bit not as t_n=A*2ⁿ+B*2ⁿ
but as: t_n=2ⁿ(A+nB)

I.e. in this case, the answer is t_n=2ⁿ(A+nB)
Where A = t₀, B = t₁/2 - t₀

On the oter issue, with the D/(A-B-C), it does work.
Consider t_n+2=t_n+1+2t_n + 3
=> D/(A-B-C) = -3/2

a series like this goes: 1, 1, 6, 11, 26,...
With the formula:
t_n = X*Rⁿ + Y*Sⁿ + D/(A-B-C)
Filling in values:
t_n = (5/6)*(-1ⁿ) + (5/3)*(2ⁿ) - 3/2

Now, not only do you have a fraction in -3/2, but also 5/6 and 5/3.
However, you will notice that this series always produces integers. (Write it out all "/ 6", and check every n mod 6)

[bugzpodder]

bugz podder wrote:

I have a recurrence relation question.

its easy if its x_n=A*x_(n-1)+B*x_(n-2)

then you do the characteristic equation. but what about:

x_n=A*x_(n-1)+B*x_(n-2)+C??

Bugz

Soarer:
similar to the one without C.

First, and

let a_n=pn+q

Solve p, q by means of a_0 and a_1.

Afterwards, omit C, and solve

a_n=ca_n-1 + da_n-2

After solving it, it should be something like

ef^n + gh^n

Sum them up, and a_n=ef^n+gh^n+pn+q is the answer....

[sql_lall]

Sorry, didn't understand that last post. Who is Soarer?

Anway, yeah, if you get repeated roots (r) in the characteristic equation, instead of writing as Arⁿ + Brⁿ+Crⁿ + ...
You change it to:
rⁿ(A + nB + n²C+...)