Question

Let a0, a1, . . . be the sequence recursively defined by a0 = 1, a1 = 4, and an = an-1 + an-2 for n ≥ 2. Suppose an is computed (recursively) by repeatedly applying the defining recurrence. Then, the number an is eventually expressed as bna1 +cna0 for some integers bn and cn. For example, a0 = 0a1 + 1a0 so b0 = 0 and c0 = 1. Similarly, a1 = 1a1 + 0a0, so b1 = 1 and c1 = 0. We have a2 = a1 + a0 so b2 = c2 = 1.

(a) Give a recursive definition of the sequences b0, b1, . . . and c0, c1 . . ..

(b) What are the numbers bn and cn for n ≥ 2?

(c) Repeat part (a) for the sequence s0, s1, s2, . . . recursively defined by s0 = 1, s1 = 1, s2 = 1 and sn = sn-1 + sn-2 + sn-3 for n ≥ 3. Eventually sn is expressed as ans0 +bns1 +cns2. Give a recursive definition of the sequences a0, a1, . . ., b0, b1, . . . and c0, c1 . . ..

Answer 1

The sequence b0, b1, ... can be recursively defined as b0 = 0, b1 = 1, and bn = bn-1 + bn-2 for n ≥ 2; The numbers bn for n ≥ 2 are 1; The sequences a0, a1, ..., b0, b1, ..., and c0, c1, ... can all be recursively defined.

Step-by-step explanation:

(a) The sequence b0, b1, ... can be recursively defined as follows:
b0 = 0
b1 = 1
bn = bn-1 + bn-2 for n ≥ 2
(b) The numbers bn for n ≥ 2 are 1.
(c) The sequence a0, a1, ... can be recursively defined as follows:
a0 = 1
a1 = 4
an = an-1 + an-2 for n ≥ 2
The sequence b0, b1, ... can be recursively defined as follows:
b0 = 0
b1 = 1
bn = bn-1 + bn-2 for n ≥ 2
The sequence c0, c1, ... can be recursively defined as follows:
c0 = 1
c1 = 0
cn = cn-1 + cn-2 for n ≥ 2