Solutions to Problem Set 13

Math 310-01/02

10-13-2017

1. Use induction to prove that

$$1 + 4 + 7 + \cdots + (3 n + 1) = \dfrac{(n + 1)(3 n + 2)}{2} \quad\hbox{for all}\quad n \ge 0.$$

For $n = 0$ ,

$$1 + 4 + 7 + \cdots + (3 n + 1) = 1 \quad\hbox{and}\quad \dfrac{(n + 1)(3 n + 2)}{2} = 1.$$

The result holds for $n = 0$ .

Assume that $n \ge 0$ and that the result holds for n:

$$1 + 4 + 7 + \cdots + (3 n + 1) = \dfrac{(n + 1)(3 n + 2)}{2}.$$

I must prove the result for $n +
   1$ . Using the induction hypothesis, I have

$$\eqalign{ 1 + 4 + 7 + \cdots + (3 n + 1) + (3(n + 1) + 1) & = \dfrac{(n + 1)(3 n + 2)}{2} + (3(n + 1) + 1) \cr \noalign{\vskip2pt} & = \dfrac{(n + 1)(3 n + 2)}{2} + (3 n + 4) \cr \noalign{\vskip2pt} & = \dfrac{(n + 1)(3 n + 2) + 2(3 n + 4)}{2} \cr \noalign{\vskip2pt} & = \dfrac{3 n^2 + 11 n + 10}{2} \cr \noalign{\vskip2pt} & = \dfrac{(n + 2)(3 n + 5)}{2} \cr \noalign{\vskip2pt} & = \dfrac{[(n + 1) + 1][3(n + 1) + 2]}{2} \cr}$$

This proves the result for $n +
   1$ . Hence, the result is true for all $ n \ge 0$ , by induction.


2. A sequence of integers is defined by

$$x_0 = 9, \quad x_1 = -29,$$

$$x_n = -2 x_{n-1} + 15 x_{n-2} \quad\hbox{for}\quad n \ge 2.$$

Prove that for $n \ge 0$ ,

$$x_n = 2 \cdot 3^n + 7 \cdot (-5)^n.$$

For $n = 0$ ,

$$2 \cdot 3^0 + 7 \cdot (-5)^0 = 2 + 7 = 9 = x_0.$$

For $n = 1$ ,

$$2 \cdot 3^1 + 7 \cdot (-5)^1 = 6 - 35 = -29 = x_1.$$

Assume the result is true for all $k < n$ . In particular, it is true for $n - 1$ and for $n - 2$ . So

$$\eqalign{ x_n & = -2 x_{n-1} + 15 x_{n-2} \cr & = -2(2 \cdot 3^{n-1} + 7 \cdot (-5)^{n-1}) + 15(2 \cdot 3^{n-2} + 7 \cdot (-5)^{n-2}) \cr & = [(-4) \cdot 3^{n-1} + 30 \cdot 3^{n-2}] + [(-14) \cdot (-5)^{n-1} + 105 \cdot (-5)^{n-2}] \cr & = 2 \cdot 3^{n-2} [(-2) \cdot 3 + 15] + 7 \cdot (-5)^{n-2} [(-2) \cdot (-5) + 15] \cr & = 2 \cdot 3^{n-2} \cdot 9 + 7 \cdot (-5)^{n-2} \cdot 25 \cr & = 2 \cdot 3^{n-2} \cdot 3^2 + 7 \cdot (-5)^{n-2} \cdot 5^2 \cr & = 2 \cdot 3^n + 7 \cdot (-5)^n \cr}$$

This proves the result for n. Hence, the result is true for all $n \ge 0$ by induction.


Our experience is composed rather of illusions lost than of wisdom acquired. - Joseph Roux


Contact information

Bruce Ikenaga's Home Page

Copyright 2017 by Bruce Ikenaga