**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.