mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2004-04-06, 12:15   #1
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

175810 Posts
Default 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

http://mathworld.wolfram.com/LinearR...eEquation.html

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
jinydu is offline   Reply With Quote
Old 2004-04-06, 19:14   #2
FeLiNe
 
FeLiNe's Avatar
 
Dec 2003

23 Posts
Default

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, x1=-1 and x2=8 so the first term that starts with (Ax1- x2) is identical to zero and all that remains is the second term.

Last fiddled with by FeLiNe on 2004-04-06 at 19:20 Reason: I just learned how to do proper subscripts 'round'ere.
FeLiNe is offline   Reply With Quote
Old 2004-04-07, 01:32   #3
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

175810 Posts
Default

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).
jinydu is offline   Reply With Quote
Old 2004-04-07, 02:41   #4
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×32×5×13 Posts
Default

Quote:
Originally Posted by jinydu
What has made this problem difficult for me is the repeated root.
Repeated roots in difference equations are similar to repeated roots in differential equations. In this case the general solutions is

A*(-4)n + B*n*(-4)n

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)n - betan]/(beta+epsilon-beta)

=[betan + n*epsilon* betan-1 + epsilon2*?? - betan]/epsilon

= n*betan-1 + epsilon*??

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

n * betan

William
wblipp is online now   Reply With Quote
Old 2004-04-07, 06:08   #5
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2·3·293 Posts
Default

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

Thanks
jinydu is offline   Reply With Quote
Old 2004-05-15, 11:59   #6
Qbert
 
May 2004

22 Posts
Default

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?
Qbert is offline   Reply With Quote
Old 2004-05-15, 14:02   #7
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×32×5×13 Posts
Default

Quote:
Originally Posted by 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?
HTML superscript codes are supported as [sup]n[/sup], so you could write this as

c(n) = (-1)n4n-1n
wblipp is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Divisibility sequences based on recurrence relations carpetpool Combinatorics & Combinatorial Number Theory 1 2017-12-21 00:42
What's the basic LLR equation? jasong jasong 4 2012-02-20 03:33
Diophantine Equation flouran Math 7 2009-12-12 18:48
Linear recurrence on elliptic curve Unregistered Information & Answers 2 2007-01-18 17:13
A Proposal for searching Recurrence Series Primes Erasmus Factoring 3 2004-05-14 09:26

All times are UTC. The time now is 02:01.

Tue Nov 24 02:01:29 UTC 2020 up 74 days, 23:12, 4 users, load averages: 4.23, 4.02, 3.42

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.