mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)
-   -   Recurrence Equation (https://www.mersenneforum.org/showthread.php?t=2329)

 jinydu 2004-04-06 12:15

Recurrence Equation

c(n+2) = -8c(n+1) - 16c(n), c(1) = -1, c(2) = 8

Given the above recurrence equation and starting conditions, the goal is to find the solution (that is, an equation that calculates c(n) without reference to previous terms).

The characteristic polynomial is:

n^2 = -8n - 16

n^2 + 8n + 16 = 0

n = -4 (repeated root)

What has made this problem difficult for me is the repeated root. Because of the repeated root, the solution given at

[url]http://mathworld.wolfram.com/LinearRecurrenceEquation.html[/url]

doesn't work because it involves dividing by zero.

In case it helps, here are some more terms:

c(0) = 0
c(1) = -1
c(2) = 8
c(3) = -48
c(4) = 256
c(5) = -1280
c(6) = 6144
c(7) = -28672

Also, the ratio between successive terms appears to be approaching some number close to -4.

Thanks

 FeLiNe 2004-04-06 19:14

I'm probably just missing something obvious somewhere, but what is wrong with eq. (11) on the Mathworld page? In the situation you present, A=-8, x[sub]1[/sub]=-1 and x[sub]2[/sub]=8 so the first term that starts with (Ax[sub]1[/sub]- x[sub]2[/sub]) is identical to zero and all that remains is the second term.

 jinydu 2004-04-07 01:32

I meant Equation 13 (I do know of a way to adjust the formula to take account of different starting terms, but that doesn't solve the problem of dividing by zero).

 wblipp 2004-04-07 02:41

[QUOTE=jinydu]What has made this problem difficult for me is the repeated root.[/QUOTE]

Repeated roots in difference equations are similar to repeated roots in differential equations. In this case the general solutions is

A*(-4)[sup]n[/sup] + B*n*(-4)[sup]n[/sup]

You pick A and B to match the first two terms.

One way to derive this is to take the two root solution with alpha = beta + epsilon and figure out what happens in the limit as epsilon goes to zero. You have
[(beta+epsilon)[sup]n[/sup] - beta[sup]n[/sup]]/(beta+epsilon-beta)

=[beta[sup]n[/sup] + n*epsilon* beta[sup]n-1[/sup] + epsilon[sup]2[/sup]*?? - beta[sup]n[/sup]]/epsilon

= n*beta[sup]n-1[/sup] + epsilon*??

Absobing a factor of beta into the constant, in the limit this is proportional to

n * beta[sup]n[/sup]

William

 jinydu 2004-04-07 06:08

Ok, that's the right answer (proven by induction).

Thanks

 Qbert 2004-05-15 11:59

Just for final clarification,
c(n)=(-1)^n*4^(-1 + n)*n
c(n)=(-1)**n*4**(-1 + n)*n

Is TeX form or even better MathML form possible to post?

 wblipp 2004-05-15 14:02

[QUOTE=Qbert]Just for final clarification,
c(n)=(-1)^n*4^(-1 + n)*n
c(n)=(-1)**n*4**(-1 + n)*n

Is TeX form or even better MathML form possible to post?[/QUOTE]

HTML superscript codes are supported as [sup]n[/sup], so you could write this as

c(n) = (-1)[sup]n[/sup]4[sup]n-1[/sup]n

 All times are UTC. The time now is 14:41.