5.3 Recursive Definitions and Structural Induction

p365
Ex: 1, 2, 3, 5

EXAMPLE 1
Suppose that ff is defined recursively by

f(0)=3f(n+1)=2f(n)+3\begin{aligned} f(0)&=3\\ f(n+1) &= 2f(n) + 3 \end{aligned}

Find f(1),f(2),f(3)f(1), f(2), f(3) and f(4)f(4).

EXAMPLE 2
Give a recursive definition of ana^n, where aa is a nonzero real number and nn is a nonnegative integer.
Solution: The recursive definition contains two parts. First a0a_0 is specified, namely, a0=1a^0 = 1. Then the rule for finding a n+1 from ana^n, namely, an+1=a⋅ana^{n+1} = a \cdot a^n, for n=0,1,2,3,⋯n = 0, 1, 2, 3, \cdots, is given. These
two equations uniquely define ana^n for all nonnegative integers nn.

EXAMPLE 3
Give a recursive definition of ∑k=0nak\sum\limits_{k=0}^n a_k.
Solution: The first part of the recursive definition is ∑k=00=a0\sum\limits_{k=0}^0 = a_0.
The second part is ∑k=0n+1ak=(∑k=0nak)+an+1\sum\limits_{k=0}^{n+1} a_k = \left(\sum\limits_{k=0}^n a_k \right)+ a_{n+1}

EXAMPLE 5
Consider the subset SS of the set of integers recursively defined by
Basic Step: 3∈S3 \in S.
Recursive Step: If x∈Sx \in S and y∈Sy \in S, then x+y∈Sx+y \in S.
The new elements found to be in S are 33 by the basis step, 3+3=63 + 3 = 6 at the first application of the recursive step, 3+6=6+3=93 + 6 = 6 + 3 = 9 and 6+6=126 + 6 = 12 at the second application of the recursive step, and so on. We will show in Example 10 that S is the set of all positive multiples of 33.

Homework

p379: 12, 13, 15, 48, 49, 50

In Exercises 12–19 fn is the nth Fibonacci number.
12. Prove that f12+f22+⋯+fn2=fnfn+1f_1^2 + f_2^2 + \cdots + f_n^2 = f_nf_{n+1} when nn is a positive integer.

Solution

Proof:
Let P(n)P(n) be the statement f12+f22+⋯+fn2=fnfn+1f_1^2 + f_2^2 + \cdots + f_n^2 = f_nf_{n+1} for all positive integer nn.
Basic step. P(1)P(1) is true, because f12=12=1⋅1=f1f2f_1^2 = 1^2 = 1 \cdot 1 = f_1f_2.
Hypothesis. Assume P(n)P(n) is true for n=kn=k

f12+f22+⋯+fk2=fkfk+1f_1^2 + f_2^2 + \cdots + f_k^2 = f_kf_{k+1}

Inductive step We need to prove P(k+1)P(k+1), namely, f12+f22+⋯+fk+12=fk+1fk+2f_1^2 + f_2^2 + \cdots + f_{k+1}^2 = f_{k+1}f_{k+2}, is true.

f12+f22+⋯+fk+12=f12+f22+⋯+fk2+fk+12=fkfk+1+fk+12By Hypothesis=fk+1(fk+fk+1)Common factor fk+1=fk+1fk+2Definition of Fabonacci Function\begin{aligned} &f_1^2 + f_2^2 + \cdots + f_{k+1}^2\\ &= f_1^2 + f_2^2 + \cdots + f_k^2 + f_{k+1}^2\\ &= f_kf_{k+1} + f_{k+1}^2 &\text{By Hypothesis}\\ &= f_{k+1}(f_k + f_{k+1}) &\text{Common factor } f_{k+1}\\ &= f_{k+1}f_{k+2} &\text{Definition of Fabonacci Function} \end{aligned}

By induction, P(n)P(n) is true.

13. Prove that f1+f3+⋯+f2n−1=f2nf_1 + f_3 + \cdots + f_{2n-1} = f_{2n} when nn is a positive integer.

Solution

Proof:
Let P(n)P(n) be the statement f1+f3+⋯+f2n−1=f2nf_1 + f_3 + \cdots + f_{2n-1} = f_{2n} for all positive integer nn.
Basic step. P(1)P(1) is true, because f12=12=1=f2f_1^2 = 1^2 = 1 = f_2.
Hypothesis. Assume P(n)P(n) is true for n=kn=k

f1+f3+⋯+f2k−1=f2kf_1 + f_3 + \cdots + f_{2k-1} = f_{2k}

Inductive step We need to prove P(k+1)P(k+1), namely, f1+f3+⋯+f2k+1=f2k+2f_1 + f_3 + \cdots + f_{2k+1} = f_{2k+2}, is true.

f1+f3+⋯+f2k+1=f1+f3+⋯+f2k−1+f2k+1=f2k+f2k+1By Hypothesis=f2k+2Definition of Fabonacci Function\begin{aligned} &f_1 + f_3 + \cdots + f_{2k+1}\\ &= f_1 + f_3 + \cdots + f_{2k-1} + f_{2k+1}\\ &= f_{2k} + f_{2k+1} &\text{By Hypothesis}\\ &= f_{2k+2} &\text{Definition of Fabonacci Function} \end{aligned}

By induction, P(n)P(n) is true.

15. Show that f0f1+f1f2+⋯+f2n−1f2n=f2n2f_0f_1 + f_1f_2 + \cdots + f_{2n-1}f_{2n} = f_{2n}^2 when nn is a positive integer.

Solution

Proof:
Let P(n)P(n) be the statement f0f1+f1f2+⋯+f2n−1f2n=f2n2f_0f_1 + f_1f_2 + \cdots + f_{2n-1}f_{2n} = f_{2n}^2 for all positive integer nn.
Basic step. P(1)P(1) is true, because f0f1+f1f2=0⋅1+1⋅1=1=f22f_0f_1 + f_1f_2 = 0 \cdot 1 + 1 \cdot 1 = 1 = f_2^2.
Hypothesis. Assume P(n)P(n) is true for n=kn=k

f0f1+f1f2+⋯+f2k−1f2k=f2k2f_0f_1 + f_1f_2 + \cdots + f_{2k-1}f_{2k} = f_{2k}^2

Inductive step We need to prove P(k+1)P(k+1), namely, f0f1+f1f2+⋯+f2k+1f2k+2=f2k+22f_0f_1 + f_1f_2 + \cdots + f_{2k+1}f_{2k+2} = f_{2k+2}^2, is true.

f0f1+f1f2+⋯+f2k+1f2k+2=f0f1+f1f2+⋯+f2k−1f2k+f2kf2k+1+f2k+1f2k+2=f2k2+f2kf2k+1+f2k+1f2k+2By Hypothesis=f2k(f2k+f2k+1)+f2k+1f2k+2Common factor f)2k=f2kf2k+2+f2k+1f2k+2Definition of Fabonacci Function=f2k+2(f2k+f2k+1)Common factor=f2k+22Definition of Fabonacci Function\begin{aligned} &f_0f_1 + f_1f_2 + \cdots + f_{2k+1}f_{2k+2}\\ &= f_0f_1 + f_1f_2 + \cdots + f_{2k-1}f_{2k} + f_{2k}f_{2k+1} + f_{2k+1}f_{2k+2}\\ &= f_{2k}^2 + f_{2k}f_{2k+1} + f_{2k+1}f_{2k+2} &\text{By Hypothesis}\\ &= f_{2k}(f_{2k} + f_{2k+1}) + f_{2k+1}f_{2k+2} &\text{Common factor }f){2k} \\ &= f_{2k}f_{2k+2} + f_{2k+1}f_{2k+2} &\text{Definition of Fabonacci Function}\\ &= f_{2k+2}(f_{2k} + f_{2k+1}) &\text{Common factor}\\ &= f_{2k+2}^2 &\text{Definition of Fabonacci Function} \end{aligned}

By induction, P(n)P(n) is true.

Consider an inductive definition of a version of Ackermann's function. This function was named after Wilhelm Ackermann, a German mathematician who was a student of the great mathematician David Hilbert. Ackermann's function plays an important role in the theory of recursive functions and in the study of the complexity of certain algorithms involving set unions. (There are several different variants of this function. All are called Ackermann's function and have similar properties even though their values do not always agree.)

A(m,n)={2nif m=00if m⩾1 and n=02if m⩾1 and n=1A(m−1,A(m,n−1)),if m⩾1 and n⩾2\begin{aligned} &A(m,n) = \begin{cases} 2n &\text{if } m=0\\ 0 &\text{if } m\ges 1 \text{ and } n = 0\\ 2 &\text{if } m\ges 1 \text{ and } n = 1 \end{cases}\\ &A(m-1, A(m, n-1)), \quad\text{if } m\ges 1 \text{ and } n \ges 2 \end{aligned}

Exercises 48–55 involve this version of Ackermann's function.
48. Find these values of Ackermann's function.
a. A(1,0)A(1, 0)   b. A(0,1)A(0, 1)   c. A(1,1)A(1, 1)   d. A(2,2)A(2, 2)

Solution

a. A(1,0)=0A(1, 0) = 0   b. A(0,1)=2⋅1=2A(0, 1) = 2\cdot 1= 2   c. A(1,1)=2A(1, 1) = 2
d.

A(2,2)=A(2−1,A(2,2−1))=A(1,A(2,1))=A(1,2)=A(0,A(1,1))=A(0,2)=2⋅2=4\begin{aligned} A(2, 2) &= A(2-1, A(2, 2-1)) \\ &= A(1, A(2, 1)) \\ &= A(1, 2)\\ &= A(0, A(1, 1)) \\ &= A(0, 2) \\ &= 2 \cdot 2 = 4 \end{aligned}

49. Show that A(m,2)=4A(m, 2) = 4 whenever m⩾1m \ges 1.

Solution

Proof:
Let P(m)P(m) be the statement A(m,2)=4A(m, 2) = 4 for every mm greater than or equal to 1.
Basic step. P(1)P(1) is true, because A(1,2)=A(0,A(1,1))=A(0,2)=4A(1, 2) = A(0, A(1, 1)) = A(0, 2) = 4.
Hypothesis. Assume P(k)P(k) is true for m=km=k

A(k,2)=4A(k, 2) = 4

Inductive step We need to prove P(k+1)P(k+1), namely, A(k+1,2)=4A(k+1, 2) = 4, is true.

A(k+1,2)=A(k,A(k+1,1))=A(k,2)Definition of Ackermann’s function=4By hypothesis\begin{aligned} A(k+1, 2) &= A(k, A(k+1, 1)) \\ &= A(k, 2) &\text{Definition of Ackermann’s function}\\ &= 4 &\text{By hypothesis} \end{aligned}

By induction, P(m)P(m) is true.

50. Show that A(1,n)=2nA(1, n) = 2^n whenever n⩾1n \ges 1.

Solution

Proof:
Let P(n)P(n) be the statement A(1,n)=2nA(1, n) = 2^n for every nn greater than or equal to 1.
Basic step. P(1)P(1) is true, because A(1,1)=2=21A(1, 1) = 2 = 2^1.
Hypothesis. Assume P(k)P(k) is true for n=kn=k

A(1,k)=2kA(1, k) = 2^k

Inductive step We need to prove P(k+1)P(k+1), namely, A(1,k+1)=2k+1A(1, k+1) = 2^{k+1}, is true.

A(1,k+1)=A(0,A(1,k))=A(0,2k)By hypothesis=2⋅2kDefinition of Ackermann’s function=2k+1\begin{aligned} A(1, k+1) &= A(0, A(1, k)) \\ &= A(0, 2^k) &\text{By hypothesis}\\ &= 2 \cdot 2^k &\text{Definition of Ackermann’s function}\\ &= 2^{k+1} \end{aligned}

By induction, P(n)P(n) is true.