Saturday, November 4, 2023

HP 15C and Casio fx-9750GIII: Solving Recurrence Relations

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.