HP 15C and Casio fx-9750GIII: Solving Recurrence Relations
Introduction
The following program attempts to find a closed-form formula to the recurrence relation:
(I)
a_n + P × a_n-1 + Q × a_n-2 = 0
or
(II)
a_n = -P × a_n-1 + -Q × a_n-2
Without loss of generality, usually P and Q in the latter form (II) are presented as positive constants.
Two initial conditions are provided, a_0 and a_1 (where n = 0 and n = 1, respectively).
Equation (I) can be transformed into the characteristic equation:
x^2 + P × x + Q = 0
where the roots are:
x = ( -P ± √(P^2 - 4 × Q)) ÷ 2
and the roots are x = S and x = T. Assume that the roots S and T are real numbers.
If S ≠ T, the solution is in the form of:
a_n = B × S^n + C × T^n
where B and C are determined by the equations:
a_0 = B + C
a_1 = B × S + C × T
If S = T, the solution is in the form of:
a_n = B × S^n + C × n × S^n
where B and C are determined by the equations:
a_0 = B
a_1 = S × (B + C)
HP 15C: Solving Recurrence Relations
Store values to the following registers:
R1 = P
R2 = Q
R3 = I
R4 = J
Output registers:
R5 = S
R6 = T
R7 = B
R8 = C
Code:
Step : Key : Code
001 : LBL A : 42,21,11 (solve for S, T)
002 : RCL 1 : 45,1
003 : x^2 : 43,11
004 : 4 : 4
005 : RCL× 2 : 45,20, 2
006 : - : 30
007 : √ : 11
008 : STO 0 : 44, 0
009 : RCL- 1 : 45,30, 1
010 : 2 : 2
011 : ÷ : 10
012 : STO 5 : 44, 5
013 : RCL- 0 : 45,30, 0
014 : STO 6 : 44, 6
015 : RCL 5 : 45, 5
016 : TEST 6 : 43,30, 6 (x ≠ y)
017 : GTO 1 : 22, 1
018 : RCL 3 : 45, 3 (if S = T, solve for B, C)
019 : STO 7 : 44, 7
020 : RCL 4 : 45, 4
021 : RCL 5 : 45, 5
022 : RCL× 7 : 45,20, 7
023 : - : 30
024 : RCL÷ 5 : 45,10, 5
025 : STO 8 : 44, 8
026 : GTO 2 : 22, 2
027 : LBL 1 : 42,21, 1 (if S≠T, solve for B, C)
028 : RCL 6 : 45, 6
029 : RCL× 3 : 45,20, 3
030 : RCL- 4 : 45,30, 4
031 : RCL 6 : 45, 6
032 : RCL- 5 : 45,30, 5
033 : ÷ : 10
034 : STO 7 : 44, 7
035 : RCL 5 : 45, 5
036 : CHS : 16
037 : RCL× 3 : 45,20, 3
038 : RCL+ 4 : 45,40, 4
039 : RCL 6 : 45, 6
040 : RCL- 5 : 45,30, 5
041 : ÷ : 10
042 : STO 8 : 44, 8
043 : LBL 2 : 42,21, 2 (view results)
044 : RCL 7 : 45, 7
045 : R/S : 31
046 : RCL 5 : 45, 5
047 : R/S : 31
048 : RCL 8 : 45, 8
049 : R/S : 31
050 : RCL 6 : 45, 6
051 : RTN : 45, 32
Casio fx-9750GIII Program: RCHAR
Text file listing:
'ProgramMode:RUN
"2023_-_09_-_26 EWS"
ClrText
"SOLVE"
"A(N) _+_ P_*_A(N_-_1) "
"_+_ Q_*_A(N_-_2) = 0"
"P"?->P
"Q"?->Q
"A(0)"?->I
"A(1)"?->J
(-P+Sqrt(P^<2>-4Q))/2->S
(-P-Sqrt(P^<2>-4Q))/2->T
If S<>T
Then
(T*I-J)/(T-S)->B
(-S*I+J)/(T-S)->C
ClrText
Locate 1,3,"B_*_S_^_N _+_ C_*_T_^_N"
Else
I->B
(J-S*B)/S->C
ClrText
Locate 1,3,"B_*_S_^_N _+_ C_*_N_*_T_^_N"
IfEnd
Locate 1,4,"B="
Locate 4,4,B
Locate 1,5,"S="
Locate 4,5,S
Locate 1,6,"C="
Locate 4,6,C
Locate 1,7,"T="
Locate 4,7,T
Notes:
This is the text file from Casio fx-9750GIII.
_: space
->: store (→)
^<2>: ^2
Sqrt: √
<>: ≠
Examples
1. a_n - 11 × a_n-1 + 24 = 0, a_0 = 3, a_1 = 8
Characteristic Equation: x^2 - 11x + 24 = 0
Roots: S = 3, T =-8
Different Roots
3 = B + C
8 = 3 × B - 8 × C
B = -0.2, C = 3.2
Solution:
a_n = -0.2 × 8^n + 3.2 × 3^n
2. a_n + 6 × a_n-1 + 9 × a_n-2 = 0, a_0 = 2, a_ 11
Characteristic Equation: x^2 + 6x + 9 = 0
Roots: S = T = -3
Same Roots
2 = B
10 = -3 × (B + C)
B = 2, C = -16/3 ≈ -4.3333
Solution:
a_n = 2 × (-3)^n - 16/3 × n × (-3)^n
3. a_n - 6 × a_n-1 + 4 × a_n-2 = 0, a_0 = 1, a_1 = 15
Characteristic Equation: x^2 - 6x + 4 = 0
Roots:
S = 3 + √5 ≈ 5.236067977
T = 3 - √5 ≈ 0.7639320225
Different Roots
1 = B + C
15 = (3 + √5) × B - (3 - √5) × C
B ≈ 3.183281573
C ≈ -2.183281573
Solution:
a_n ≈
3.183281573 × 5.236067977^n - 2.183281573 × 0.7639320225^n
Source
Levin, Oscar. "2.4 Recurrence Relations" Discrete Mathematics: An Open Introduction openmathbooks.org University of Northern Colorado. Retrieved August 30, 2023. https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/2%3A_Sequences/2.4%3A_Solving_Recurrence_Relations
Eddie
All original content copyright, © 2011-2023. Edward Shore. Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited. This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.