Mathematics for Computer Science

Chapter 21 Recurrences876

This suggests that there are at least two different solutions to the recurrence, ne-
glecting the boundary conditions.

f.n/D

1 C

p

5

2

!n

or f.n/D

1

p

5

2

!n

A charming features of homogeneous linear recurrences is that any linear com-
bination of solutions is another solution.

Theorem 21.3.1. Iff.n/andg.n/are both solutions to a homogeneous linear
recurrence, thenh.n/Dsf.n/Ctg.n/is also a solution for alls;t 2 R.

Proof.

h.n/Dsf.n/Ctg.n/

Ds.a 1 f.n1/C


Cadf.nd//Ct.a 1 g.n1/C


Cadg.nd//

Da 1 .sf.n1/Ctg.n1//C


Cad.sf.nd/Ctg.nd//

Da 1 h.n1/C


Cadh.nd/

The first step uses the definition of the functionh, and the second uses the fact that
f andgare solutions to the recurrence. In the last two steps, we rearrange terms
and use the definition ofhagain. Since the first expression is equal to the last,his
also a solution to the recurrence. 

The phenomenon described in this theorem—a linear combination of solutions is
another solution—also holds for many differential equations and physical systems.
In fact, linear recurrences are so similar to linear differential equations that you can
safely snooze through that topic in some future math class.
Returning to the Fibonacci recurrence, this theorem implies that

f.n/Ds

1 C

p

5

2

!n

Ct

1

p

5

2

!n

is a solution for all real numberssandt. The theorem expanded two solutions to
a whole spectrum of possibilities! Now, given all these options to choose from,
we can find one solution that satisfies the boundary conditions,f.0/ D 1 and
f.1/D 1. Each boundary condition puts some constraints on the parameterssand
t. In particular, the first boundary condition implies that

f.0/Ds

1 C

p

5

2

! 0

Ct

1

p

5

2

! 0

DsCtD1: