Solve the first-order linear recurrence relation: S n+1 = 5 S n + 1, with S 0 =1. You may use the general solution given

Solve the first-order linear recurrence relation: S n+1 = 5 S n + 1, with S 0 =1. You may use the general solution given on P.342. Transcribed Image Text: This can be proved by MI – if for some ke P, S = aki+ ak-1 c +
C +… + ac + c then
Sk+1 = aSk + c
= a [a*I + a*=\c + a*~?c+ … + ac +
= ak+’ I + a*c + ak-‘c + . . + a²c + ac + c.
+ a*-\c + a*-²c + . + ac +
„k-2
´c +
+ c
°c +
Thus, (8.2.2) is correct. Hence, if S is any sequence on N
satisfying (8.2.1), then for vn e P
if a = 1, S, = 1″I + 1″-‘c + 1″-?c + … + lc + c
= I + nc,
// And this formula works for So
%3D
and if a + 1, S, = a”I + a”-‘c + a”-?c + … + ac + c
%3D
// and from Theorem 3.6.9
1- a”
с
3 а”1 + с-
1 – a
C
a”
a”I +
=
1 — а
C
= d” |1- +
/| And this formula works for So
1- a
Therefore, the general solution of the recurrence equation
S n+1
aS n + c
for V n e N
(8.2.1)
is given in two parts:
Pg. 342
if a = 1,
Sn = I + nc
for Vn e N;
if a + 1,
S, = a”A +
for V n e N.
When a = 1, any particular solution is obtained by
determining a specific, numerical value for I. In fact, a particular
solution is determined by a specific, numerical value / for any
(particular) entry, S;. Solving the equation
J = I + jc for I,
I = J – jc.
// since S; = I + jc
// where So = I
we get
// One particular “particular solution” has / = 0.
When a + 1, any particular solution is obtained by
determining a specific, numerical value for A; if the starting value
Iis given, then A = I – . In fact, a particular solution is
%3D
determined by a specific, numerical value / for any (particular)
entry, Sj. Solving the equation
J = Aa’
+
1 —а
for A,
we get
A =
// But what if a =
0?
// One particular “particular solution” has A = o.
%3D
Example 8.2.1:
The recurrence equation for the number of moves in the
Towers of Hanoi problem is a first-order linear recurrence
equation:
The Towers of Hanoi
Tn = 2Tµ-1 + 1.
Here a = 2 and c = 1, so = 2
= -1, and an. sequence T
1-a Transcribed Image Text: 8.2 Solving First-Order Linear Recurrence
Equations
A first-order linear recurrence equation relates consecutive entries
in a sequence by an equation of the form
S n+1 = aS n + c
for V n in the domain of S.
(8.2.1)
But let’s assume that the domain of S is N. Let’s also assume
that a * 0; otherwise, S, = c for Vn > 0, and the solutions to
(8.2.1) are not very interesting.
// are they?
We saw in Chap. 3, that when a = 1, any sequence satisfying
(8.2.1) is an arithmetic sequence, and when S is defined on N and
So is some initial value /,
Sn
= I + nc
for Vn e N.
// Theorem 3.6.4
Also, when c = 0, any sequence satisfying (8.2.1) is a geometric
sequence, and when S is defined on N and So is some initial value
I,
Sn = a” I
for V n e N.
// Theorem 3.6.7
Furthermore, Theorem 3.6.8gives a formula for the sum of
the first (n + 1) terms of a geometric series when a + 1:
a”+1
– 1
a°1 + a’I + a²I + … + a”I = I (1 + a + a² + …
+ a”) = 1-
а — 1
In particular, 1 + ½ + (½)* + (‘2) + … + ‘2)” = [(“2)* -1|/[2-1]
(2)’
(‘2) = (C’2)” – 1|/[‘2 – 1]
\n+1
%D
= 2 – (‘½)” .
Equation 8.2.1 says how the sequence continues, after
starting with some initial value / but doesn’t restrict the value of
I; hence, there is an infinite number of solutions.
A general solution is an algebraic description of all such
solution sequences.
If S is any sequence on N satisfying (8.2.1), then denoting So
by I, we have
S1 = aSo + c
S2 = aS 1 + c = a[al + c] + c
= al + c,
— а?1 + ас + с,
S3 = aS2 + c = a
[a* –
+c]
+c = a³I+ a²c + ac + c.
+ ас
So we might conjecture
S, = a”I + a”¯’c+a”=²c + . .. + ac + c
for V n e P. (8.2.2)
n-
This can be proved by MI – if for some ke P, Sk = akI+ a*-1 c +
ak-2 c+ … + ac + c then
Sk+1 = aSk + c