20040406, 12:15  #1 
Dec 2003
Hopefully Near M48
3336_{8} Posts 
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 
20040406, 19:14  #2 
Dec 2003
23 Posts 
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_{1}=1 and x_{2}=8 so the first term that starts with (Ax_{1} x_{2}) is identical to zero and all that remains is the second term.
Last fiddled with by FeLiNe on 20040406 at 19:20 Reason: I just learned how to do proper subscripts 'round'ere. 
20040407, 01:32  #3 
Dec 2003
Hopefully Near M48
3336_{8} Posts 
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).

20040407, 02:41  #4  
"William"
May 2003
New Haven
3·787 Posts 
Quote:
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}  beta^{n}]/(beta+epsilonbeta) =[beta^{n} + n*epsilon* beta^{n1} + epsilon^{2}*??  beta^{n}]/epsilon = n*beta^{n1} + epsilon*?? Absobing a factor of beta into the constant, in the limit this is proportional to n * beta^{n} William 

20040407, 06:08  #5 
Dec 2003
Hopefully Near M48
6DE_{16} Posts 
Ok, that's the right answer (proven by induction).
Thanks 
20040515, 11:59  #6 
May 2004
100_{2} Posts 
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? 
20040515, 14:02  #7  
"William"
May 2003
New Haven
3·787 Posts 
Quote:
c(n) = (1)^{n}4^{n1}n 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Divisibility sequences based on recurrence relations  carpetpool  Combinatorics & Combinatorial Number Theory  1  20171221 00:42 
What's the basic LLR equation?  jasong  jasong  4  20120220 03:33 
Diophantine Equation  flouran  Math  7  20091212 18:48 
Linear recurrence on elliptic curve  Unregistered  Information & Answers  2  20070118 17:13 
A Proposal for searching Recurrence Series Primes  Erasmus  Factoring  3  20040514 09:26 