2.E: Sequences (Exercises)

$\def\d{\displaystyle}$
$\newcommand{\f}[1]{\mathfrak #1}$
$\newcommand{\s}[1]{\mathscr #1}$
$\def\N{\mathbb N}$
$\def\B{\mathbf{B}}$
$\def\circleA{(-.5,0) circle (1)}$
$\def\Z{\mathbb Z}$
$\def\circleAlabel{(-1.5,.6) node[above]{$A$}}$
$\def\Q{\mathbb Q}$
$\def\circleB{(.5,0) circle (1)}$
$\def\R{\mathbb R}$
$\def\circleBlabel{(1.5,.6) node[above]{$B$}}$
$\def\C{\mathbb C}$
$\def\circleC{(0,-1) circle (1)}$
$\def\F{\mathbb F}$
$\def\circleClabel{(.5,-2) node[right]{$C$}}$
$\def\A{\mathbb A}$
$\def\twosetbox{(-2,-1.5) rectangle (2,1.5)}$
$\def\X{\mathbb X}$
$\def\threesetbox{(-2,-2.5) rectangle (2,1.5)}$
$\def\E{\mathbb E}$
$\def\O{\mathbb O}$
$\def\U{\mathcal U}$
$\def\pow{\mathcal P}$
$\def\inv{^{-1}}$
$\def\nrml{\triangleleft}$
$\def\st{:}$
$\def\~{\widetilde}$
$\def\rem{\mathcal R}$
$\def\sigalg{$\sigma$-algebra }$
$\def\Gal{\mbox{Gal}}$
$\def\iff{\leftrightarrow}$
$\def\Iff{\Leftrightarrow}$
$\def\land{\wedge}$
$\def\And{\bigwedge}$
$\def\entry{\entry}$
$\def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}$
$\def\Vee{\bigvee}$
$\def\VVee{\d\Vee\mkern-18mu\Vee}$
$\def\imp{\rightarrow}$
$\def\Imp{\Rightarrow}$
$\def\Fi{\Leftarrow}$
$\def\var{\mbox{var}}$
$\def\Th{\mbox{Th}}$
$\def\entry{\entry}$
$\def\sat{\mbox{Sat}}$
$\def\con{\mbox{Con}}$
$\def\iffmodels{\bmodels\models}$
$\def\dbland{\bigwedge \!\!\bigwedge}$
$\def\dom{\mbox{dom}}$
$\def\rng{\mbox{range}}$
$\def\isom{\cong}$
$\DeclareMathOperator{\wgt}{wgt}$
$\newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}}$
$\newcommand{\va}[1]{\vtx{above}{#1}}$
$\newcommand{\vb}[1]{\vtx{below}{#1}}$
$\newcommand{\vr}[1]{\vtx{right}{#1}}$
$\newcommand{\vl}[1]{\vtx{left}{#1}}$
$\renewcommand{\v}{\vtx{above}{}}$
$\def\circleA{(-.5,0) circle (1)}$
$\def\circleAlabel{(-1.5,.6) node[above]{$A$}}$
$\def\circleB{(.5,0) circle (1)}$
$\def\circleBlabel{(1.5,.6) node[above]{$B$}}$
$\def\circleC{(0,-1) circle (1)}$
$\def\circleClabel{(.5,-2) node[right]{$C$}}$
$\def\twosetbox{(-2,-1.4) rectangle (2,1.4)}$
$\def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}$
$\def\ansfilename{practice-answers}$
$\def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }$
$\renewcommand{\bar}{\overline}$
$\newcommand{\card}[1]{\left| #1 \right|}$
$\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}$
$\newcommand{\lt}{<}$
$\newcommand{\gt}{>}$
$\newcommand{\amp}{&}$

$\newcommand{\hexbox}[3]{ \def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2} \def\y{-\r*#1-sin{30}*\r*#1} \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle; \draw (\x,\y) node{#3}; }$

$\renewcommand{\bar}{\overline}$
$\newcommand{\card}[1]{\left| #1 \right|}$
$\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}$
$\newcommand{\lt}{<}$
$\newcommand{\gt}{>}$
$\newcommand{\amp}{&}$

2.1: Definitions

1

Find the closed formula for each of the following sequences by relating them to a well known sequence. Assume the first term given is $a_1\text{.}$

1. $2, 5, 10, 17, 26, \ldots$
2. $0, 2, 5, 9, 14, 20, \ldots$
3. $8, 12, 17, 23, 30,\ldots$
4. $1, 5, 23, 119, 719,\ldots$

Answer

1. $a_n = n^2 + 1\text{.}$
2. $a_n = \frac{n(n+1)}{2} - 1\text{.}$
3. $a_n = \frac{(n+2)(n+3)}{2} + 2\text{.}$
4. $a_n = (n+1)! - 1$ (where $n! = 1 \cdot 2 \cdot 3 \cdots n$).

2

For each sequence given below, find a closed formula for $a_n\text{,}$ the $n$th term of the sequence (assume the first terms are $a_0$) by relating it to another sequence for which you already know the formula. In each case, briefly say how you got your answers.

1. 4, 5, 7, 11, 19, 35, …
2. 0, 3, 8, 15, 24, 35, …
3. 6, 12, 20, 30, 42, …
4. 0, 2, 7, 15, 26, 40, 57, … (Cryptic Hint: these might be called “house numbers”)

3

The Fibonacci sequence is $0, 1, 1, 2, 3, 5, 8, 13, \ldots$ (where $F_0 = 0$).

1. Give the recursive definition for the sequence.
2. Write out the first few terms of the sequence of partial sums: $0\text{,}$ $0+1\text{,}$ $0+1+1\text{,}$…
3. Give a closed formula for the sequence of partial sums in terms of $F_n$ (for example, you might say $F_0 + F_1 + \cdots + F_n = 3F_{n-1}^2 + n\text{,}$ although that is definitely not correct).

Answer

1. $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0$ and $F_1 = 1\text{.}$
2. $0, 1, 2, 4, 7, 12, 20, \ldots.$
3. $F_0 + F_1 + \cdots + F_n = F_{n+2} - 1.$

4

Consider the three sequences below. For each, find a recursive definition. How are these sequences related?

1. $2, 4, 6, 10, 16, 26, 42, \ldots\text{.}$
2. $5, 6, 11, 17, 28, 45, 73, \ldots\text{.}$
3. $0, 0 , 0 , 0 , 0 , 0 , 0 ,\ldots\text{.}$

Answer

The sequences all have the same recurrence relation: $a_n = a_{n-1} + a_{n-2}$ (the same as the Fibonacci numbers). The only difference is the initial conditions.

5

Show that $a_n = 3\cdot 2^n + 7\cdot 5^n$ is a solution to the recurrence relation $a_n = 7a_{n-1} - 10a_{n-2}\text{.}$ What would the initial conditions need to be for this to be the closed formula for the sequence?

6

Write out the first few terms of the sequence given by $a_1 = 3\text{;}$ $a_n = 2a_{n-1} + 4\text{.}$ Then find a recursive definition for the sequence $10, 24, 52, 108, \ldots\text{.}$

7

Write out the first few terms of the sequence given by $a_n = n^2 - 3n + 1\text{.}$ Then find a closed formula for the sequence (starting with $a_1$) $0, 2, 6, 12, 20, \ldots\text{.}$

8

Find a closed formula for the sequence with recursive definition $a_n = 2a_{n-1} - a_{n-2}$ with $a_1 = 1$ and $a_2 = 2\text{.}$

9

Find a recursive definition for the sequence with closed formula $a_n = 3 + 2n\text{.}$ Bonus points if you can give a recursive definition in which makes use of two previous terms and no constants.

2.2: Arithmetic and Geometric Sequences

1

Consider the sequence $5, 9, 13, 17, 21, \ldots$ with $a_1 = 5$

1. Give a recursive definition for the sequence.
2. Give a closed formula for the $n$th term of the sequence.
3. Is $2013$ a term in the sequence? Explain.
4. How many terms does the sequence $5, 9, 13, 17, 21, \ldots, 533$ have?
5. Find the sum: $5 + 9 + 13 + 17 + 21 + \cdots + 533\text{.}$ Show your work.
6. Use what you found above to find $b_n\text{,}$ the $n^{th}$ term of $1, 6, 15, 28, 45, \ldots\text{,}$ where $b_0 = 1$

Answer

1. $a_n = a_{n-1} + 4$ with $a_1 = 5\text{.}$
2. $a_n = 5 + 4(n-1)\text{.}$
3. Yes, since $2013 = 5 + 4(503-1)$ (so $a_{503} = 2013$).
4. 133
5. $\frac{538\cdot 133}{2} = 35777\text{.}$
6. $b_n = 1 + \frac{(4n+6)n}{2}\text{.}$

2

Consider the sequence $(a_n)_{n \ge 0}$ which starts $8, 14, 20, 26, \ldots\text{.}$

1. What is the next term in the sequence?
2. Find a formula for the $n$th term of this sequence.
3. Find the sum of the first 100 terms of the sequence: $\sum_{k=0}^{99}a_k\text{.}$

Answer

1. $32\text{,}$ which is $26+6\text{.}$
2. $a_n = 8 + 6n\text{.}$
3. $30500\text{.}$ We want $8 + 14 + \cdots + 602\text{.}$ Reverse and add to get 100 sums of 610, a total of 61000, which is twice the sum we are looking for.

3

Consider the sum $4 + 11 + 18 + 25 + \cdots + 249\text{.}$

1. How many terms (summands) are in the sum?
2. Compute the sum. Remember to show all your work.

Answer

1. 36.
2. $\frac{253 \cdot 36}{2} = 4554\text{.}$

4

Consider the sequence $1, 7, 13, 19, \ldots, 6n + 7\text{.}$

1. How many terms are there in the sequence?
2. What is the second-to-last term?
3. Find the sum of all the terms in the sequence.

Answer

1. $n+2$ terms, since to get 1 using the formula $6n+7$ we must use $n=-1\text{.}$ Thus we have $n$ terms, plus the $n=0$ and $n=-1$ terms.
2. $6n+1\text{,}$ which is 6 less than $6n+7$ (or plug in $n-1$ for $n$).
3. $\frac{(6n+8)(n+2)}{2}\text{.}$ Reverse and add. Each sum gives the constant $6n+8$ and there are $n+2$ terms.

5

Find $5 + 7 + 9 + 11+ \cdots + 521\text{.}$

Answer

$68117\text{.}$ If we take $a_0 = 5\text{,}$ the terms of the sum are an arithmetic sequence with closed formula $a_n = 5+2n\text{.}$ Then $521 = a_{258}\text{,}$ for a total of 259 terms in the sum. Reverse and add to get 259 identical 526 terms, which is twice the total we seek. $526\cdot 259 = 68117$

6

Find $5 + 15 + 45 + \cdots + 5\cdot 3^{20}\text{.}$

Answer

$\frac{5-5\cdot 3^{21}}{-2}\text{.}$ Let the sum be $S\text{,}$ and compute $S - 3S = -2S\text{,}$ which causes terms except $5$ and $-5\cdot 3^{21}$ to cancel. Then solve for $S\text{.}$

7

Find $1 - \frac{2}{3} + \frac{4}{9} - \cdots + \frac{2^{30}}{3^{30}}\text{.}$

8

Find $x$ and $y$ such that $27, x, y, 1$ is part of an arithmetic sequence. Then find $x$ and $y$ so that the sequence is part of a geometric sequence. (Warning: $x$ and $y$ might not be integers.)

9

Starting with any rectangle, we can create a new, larger rectangle by attaching a square to the longer side. For example, if we start with a $2\times 5$ rectangle, we would glue on a $5\times 5$ square, forming a $5 \times 7$ rectangle:

1. Create a sequence of rectangles using this rule starting with a $1\times 2$ rectangle. Then write out the sequence of perimeters for the rectangles (the first term of the sequence would be 6, since the perimeter of a $1\times 2$ rectangle is 6 - the next term would be 10).
2. Repeat the above part this time starting with a $1 \times 3$ rectangle.
3. Find recursive formulas for each of the sequences of perimeters you found in parts (a) and (b). Don't forget to give the initial conditions as well.
4. Are the sequences arithmetic? Geometric? If not, are they close to being either of these (i.e., are the differences or ratios almost constant)? Explain.

10

Consider the sequence $2, 7, 15, 26, 40, 57, \ldots$ (with $a_0 = 2$). By looking at the differences between terms, express the sequence as a sequence of partial sums. Then find a closed formula for the sequence by computing the $n$th partial sum.

Answer

We have $2 = 2\text{,}$ $7 = 2+5\text{,}$ $15 = 2 + 5 + 8\text{,}$ $26 = 2+5+8+11\text{,}$ and so on. The terms in the sums are given by the arithmetic sequence $b_n = 2+3n\text{.}$ In other words, $a_n = \sum_{k=0}^n (2+3k)\text{.}$ To find the closed formula, we reverse and add. We get $a_n = \frac{(4+3n)(n+1)}{2}$ (we have $n+1$ there because there are $n+1$ terms in the sum for $a_n$).

11

If you have enough toothpicks, you can make a large triangular grid. Below, are the triangular grids of size 1 and of size 2. The size 1 grid requires 3 toothpicks, the size 2 grid requires 9 toothpicks.

1. Let $t_n$ be the number of toothpicks required to make a size $n$ triangular grid. Write out the first 5 terms of the sequence $t_1, t_2, \ldots\text{.}$
2. Find a recursive definition for the sequence. Explain why you are correct.
3. Is the sequence arithmetic or geometric? If not, is it the sequence of partial sums of an arithmetic or geometric sequence? Explain why your answer is correct.
4. Use your results from part (c) to find a closed formula for the sequence. Show your work.

12

Use summation ($\sum$) or product ($\prod$) notation to rewrite the following.

1. $2 + 4 + 6 + 8 + \cdots + 2n\text{.}$
2. $1 + 5 + 9 + 13 + \cdots + 425\text{.}$
3. $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{50}\text{.}$
4. $2 \cdot 4 \cdot 6 \cdot \cdots \cdot 2n\text{.}$
5. $(\frac{1}{2})(\frac{2}{3})(\frac{3}{4})\cdots(\frac{100}{101})\text{.}$

Answer

1. $\d\sum_{k=1}^n 2k\text{.}$
2. $\d\sum_{k=1}^{107} (1 + 4(k-1))\text{.}$
3. $\d\sum_{k=1}^{50} \frac{1}{k}\text{.}$
4. $\d\prod_{k=1}^n 2k\text{.}$
5. $\d\prod_{k=1}^{100} \frac{k}{k+1}\text{.}$

13

Expand the following sums and products. That is, write them out the long way.

1. $\d\sum_{k=1}^{100} (3+4k)\text{.}$
2. $\d\sum_{k=0}^n 2^k\text{.}$
3. $\d\sum_{k=2}^{50}\frac{1}{(k^2 - 1)}\text{.}$
4. $\d\prod_{k=2}^{100}\frac{k^2}{(k^2-1)}\text{.}$
5. $\d\prod_{k=0}^n (2+3k)\text{.}$

Answer

1. $\d\sum_{k=1}^{100} (3+4k) = 7 + 11 + 15 + \cdots + 403\text{.}$
2. $\d\sum_{k=0}^n 2^k = 1 + 2 + 4 + 8 + \cdots + 2^n\text{.}$
3. $\d\sum_{k=2}^{50}\frac{1}{(k^2 - 1)} = 1 + \frac{1}{3} + \frac{1}{8} + \frac{1}{15} + \cdots + \frac{1}{2499}\text{.}$
4. $\d\prod_{k=2}^{100}\frac{k^2}{(k^2-1)} = \frac{4}{3}\cdot\frac{9}{8}\cdot\frac{16}{15}\cdots\frac{10000}{9999}\text{.}$
5. $\d\prod_{k=0}^n (2+3k) = (2)(5)(8)(11)(14)\cdots(2+3n)\text{.}$

2.3: Polynomial Fitting

1

Use polynomial fitting to find the formula for the $n$th term of the sequences $(a_n)_{n \ge 0}$ below.

1. 2, 5, 11, 21, 36,…
2. 0, 2, 6, 12, 20,…
3. 1, 2, 4, 8, 15, 26 …
4. 3, 6, 12, 22, 37, …. After finding a formula here, compare to part (a).

Answer

1. Notice that the third differences are constant, so $a_n = an^3 + bn^2 + cn + d\text{.}$ Use the terms of the sequence to solve for $a, b, c,$ and $d$ to get $a_n = \frac{1}{6} (12+11 n+6 n^2+n^3)\text{.}$
2. $a_n = n^2 + n\text{.}$ Here we know that we are looking for a quadratic because the second differences are constant. So $a_n = an^2 + bn + c\text{.}$ Since $a_0 = 0\text{,}$ we know $c= 0\text{.}$ So just solve the system $$\begin{align*} 2 \amp = a + b \\ 6 \amp = 4a + 2b \end{align*}$$

2

Make up a sequences that have

1. 3, 3, 3, 3, … as its second differences.
2. 1, 2, 3, 4, 5, … as its third differences.
3. 1, 2, 4, 8, 16, … as its 100th differences.

3

Consider the sequence $1, 3, 7, 13, 21, \ldots\text{.}$ Explain how you know the closed formula for the sequence will be quadratic. Then “guess” the correct formula by comparing this sequence to the squares $1, 4, 9, 16, \ldots$ (do not use polynomial fitting).

Solution

The first differences are $2, 4, 6, 8, \ldots\text{,}$ and the second differences are $2, 2, 2, \ldots\text{.}$ Thus the original sequence is $\Delta^2$-constant, so can be fit to a quadratic.

Call the original sequence $a_n\text{.}$ Consider $a_n - n^2\text{.}$ This gives $0, -1, -2, -3, \ldots\text{.}$ That sequence has closed formula $1-n$ (starting at $n = 1$) so we have $a_n - n^2 = 1-n$ or equivalently $a_n = n^2 - n + 1\text{.}$

4

Use a similar technique as in the previous exercise to find a closed formula for the sequence $2, 11, 34, 77, 146, 247,\ldots\text{.}$

5

In their down time, ghost pirates enjoy stacking cannonballs in triangular based pyramids (aka, tetrahedrons), like those pictured here:

Note, in the picture on the right, there are some cannonballs (actually just one) you cannot see. The next picture would have 4 cannonballs you cannot see. The stacks are not hollow.

The pirates wonder how many cannonballs would be required to build a pyramid 15 layers high (thus breaking the world cannonball stacking record). Can you help?

1. Let $P(n)$ denote the number of cannonballs needed to create a pyramid $n$ layers high. So $P(1) = 1\text{,}$ $P(2) = 4\text{,}$ and so on. Calculate $P(3)\text{,}$ $P(4)$ and $P(5)\text{.}$
2. Use polynomial fitting to find a closed formula for $P(n)\text{.}$ Show your work.
3. Answer the pirate's question: how many cannonballs do they need to make a pyramid 15 layers high?

6

Suppose $a_n = n^2 + 3n + 4\text{.}$ Find a closed formula for the sequence of differences by computing $a_n - a_{n-1}\text{.}$

Answer

$a_{n-1} = (n-1)^2 + 3(n-1) + 4 = n^2 + n + 2\text{.}$ Thus $a_n - a_{n-1} = 2n+2\text{.}$ Note that this is linear (arithmetic). We can check that we are correct. The sequence $a_n$ is $4, 8, 14, 22, 32, \ldots$ and the sequence of differences is thus $4, 6, 8, 10,\ldots$ which agrees with $2n+2$ (if we start at $n = 1$).

7

Repeat the above assuming this time $a_n = an^2 + bn + c\text{.}$ That is, prove that every quadratic sequence has arithmetic differences.

8

Can you use polynomial fitting to find the formula for the $n$th term of the sequence 4, 7, 11, 18, 29, 47, …? Explain why or why not.

9

Will the $n$th sequence of differences of $2, 6, 18, 54, 162, \ldots$ ever be constant? Explain.

10

Consider the sequences $2, 5, 12, 29, 70, 169, 408,\ldots$ (with $a_0 = 2$).

1. Describe the rate of growth of this sequence.
2. Find a recursive definition for the sequence.
3. Find a closed formula for the sequence.
4. If you look at the sequence of differences between terms, and then the sequence of second differences, the sequence of third differences, and so on, will you ever get a constant sequence? Explain how you know

2.4: Solving Recurrence Relations

1

Find the next two terms in $(a_n)_{n\ge 0}$ beginning $3, 5, 11, 21, 43, 85\ldots.\text{.}$ Then give a recursive definition for the sequence. Finally, use the characteristic root technique to find a closed formula for the sequence.

Answer

171 and 341. $a_n = a_{n-1} + 2a_{n-2}$ with $a_0 = 3$ and $a_1 = 5\text{.}$ Closed formula: $a_n = \frac{8}{3}2^n + \frac{1}{3}(-1)^n\text{.}$ To find this solve the characteristic polynomial, $x^2 - x - 2\text{,}$ to get characteristic roots $x = 2$ and $x=-1\text{.}$ Then solve the system $$\begin{align*} 3 \amp = a + b\\ 5 \amp = 2a - b \end{align*}$$

2

Solve the recurrence relation $a_n = a_{n-1} + 2^n$ with $a_0 = 5\text{.}$

Answer

$a_n = 3 + 2^{n+1}\text{.}$ We should use telescoping or iteration here. For example, telescoping gives

$$\begin{align*} a_1 - a_0 \amp = 2^1\\ a_2 - a_1 \amp = 2^2\\ a_3 - a_2 \amp = 2^3\\ \vdots\amp \vdots \\ a_n - a_{n-1} \amp = 2^n \end{align*}$$

which sums to $a_n - a_0 = 2^{n+1} - 2$ (using the multiply-shift-subtract technique from Section 2.2 for the right-hand side). Substituting $a_0 = 5$ and solving for $a_n$ completes the solution.

3

Show that $4^n$ is a solution to the recurrence relation $a_n = 3a_{n-1} + 4a_{n-2}\text{.}$

Answer

We claim $a_n = 4^n$ works. Plug it in: $4^n = 3(4^{n-1}) + 4(4^{n-2})\text{.}$ This works - just simplify the right-hand side.

4

Find the solution to the recurrence relation $a_n = 3a_{n-1} + 4a_{n-2}$ with initial terms $a_0 = 2$ and $a_1 = 3\text{.}$

Answer

By the Characteristic Root Technique. $a_n = 4^n + (-1)^n\text{.}$

5

Find the solution to the recurrence relation $a_n = 3a_{n-1} + 4a_{n-2}$ with initial terms $a_0 = 5$ and $a_1 = 8\text{.}$

6

Solve the recurrence relation $a_n = 2a_{n-1} - a_{n-2}\text{.}$

1. What is the solution if the initial terms are $a_0 = 1$ and $a_1 = 2\text{?}$
2. What do the initial terms need to be in order for $a_9 = 30\text{?}$
3. For which $x$ are there initial terms which make $a_9 = x\text{?}$

7

Solve the recurrence relation $a_n = 3a_{n-1} + 10a_{n-2}$ with initial terms $a_0 = 4$ and $a_1 = 1\text{.}$

8

Suppose that $r^n$ and $q^n$ are both solutions to a recurrence relation of the form $a_n = \alpha a_{n-1} + \beta a_{n-2}\text{.}$ Prove that $c\cdot r^n + d \cdot q^n$ is also a solution to the recurrence relation, for any constants $c, d\text{.}$

9

Think back to the magical candy machine at your neighborhood grocery store. Suppose that the first time a quarter is put into the machine 1 Skittle comes out. The second time, 4 Skittles, the third time 16 Skittles, the fourth time 64 Skittles, etc.

1. Find both a recursive and closed formula for how many Skittles the nth customer gets.
2. Check your solution for the closed formula by solving the recurrence relation using the Characteristic Root technique.

10

You have access to $1 \times 1$ tiles which come in 2 different colors and $1\times 2$ tiles which come in 3 different colors. We want to figure out how many different $1 \times n$ path designs we can make out of these tiles.

1. Find a recursive definition for the sequence $a_n$ of paths of length $n\text{.}$
2. Solve the recurrence relation using the Characteristic Root technique.

11

Let $a_n$ be the number of $1 \times n$ tile designs you can make using $1 \times 1$ squares available in 4 colors and $1 \times 2$ dominoes available in 5 colors.

1. First, find a recurrence relation to describe the problem. Explain why the recurrence relation is correct (in the context of the problem).
2. Write out the first 6 terms of the sequence $a_1, a_2, \ldots\text{.}$
3. Solve the recurrence relation. That is, find a closed formula for $a_n\text{.}$

12

Consider the recurrence relation $a_n = 4a_{n-1} - 4a_{n-2}\text{.}$

1. Find the general solution to the recurrence relation (beware the repeated root).
2. Find the solution when $a_0 = 1$ and $a_1 = 2\text{.}$
3. Find the solution when $a_0 = 1$ and $a_1 = 8\text{.}$

2.5: Induction

1

Use induction to prove for all $n \in \N$ that $\d\sum_{k=0}^n 2^k = 2^{n+1} - 1\text{.}$

Solution

Proof

We must prove that $1 + 2 + 2^2 + 2^3 + \cdots +2^n = 2^{n+1} - 1$ for all $n \in \N\text{.}$ Thus let $P(n)$ be the statement $1 + 2 + 2^2 + \cdots + 2^n = 2^{n+1} - 1\text{.}$ We will prove that $P(n)$ is true for all $n \in \N\text{.}$ First we establish the base case, $P(0)\text{,}$ which claims that $1 = 2^{0+1} -1\text{.}$ Since $2^1 - 1 = 2 - 1 = 1\text{,}$ we see that $P(0)$ is true. Now for the inductive case. Assume that $P(k)$ is true for an arbitrary $k \in \N\text{.}$ That is, $1 + 2 + 2^2 + \cdots + 2^k = 2^{k+1} - 1\text{.}$ We must show that $P(k+1)$ is true (i.e., that $1 + 2 + 2^2 + \cdots + 2^{k+1} = 2^{k+2} - 1$). To do this, we start with the left-hand side of $P(k+1)$ and work to the right-hand side:

$$\begin{align*} 1 + 2 + 2^2 + \cdots + 2^k + 2^{k+1} = \amp ~ 2^{k+1} - 1 + 2^{k+1} \amp \text{by inductive hypothesis}\\ = \amp ~2\cdot 2^{k+1} - 1 \amp\\ = \amp ~ 2^{k+2} - 1 \amp \end{align*}$$

Thus $P(k+1)$ is true so by the principle of mathematical induction, $P(n)$ is true for all $n \in \N\text{.}$

2

Prove that $7^n - 1$ is a multiple of 6 for all $n \in \N\text{.}$

Solution

Proof

Let $P(n)$ be the statement “ $7^n - 1$ is a multiple of 6.” We will show $P(n)$ is true for all $n \in \N\text{.}$ First we establish the base case, $P(0)\text{.}$ Since $7^0 - 1 = 0\text{,}$ and $0$ is a multiple of 6, $P(0)$ is true. Now for the inductive case. Assume $P(k)$ holds for an arbitrary $k \in \N\text{.}$ That is, $7^k - 1$ is a multiple of 6, or in other words, $7^k - 1 = 6j$ for some integer $j\text{.}$ Now consider $7^{k+1} - 1\text{:}$

$$\begin{align*} 7^{k+1} - 1 ~ \amp = 7^{k+1} - 7 + 6 \amp \text{by cleverness:} -1 = -7 + 6\\ \amp = 7(7^k - 1) + 6 \amp \text{factor out a 7 from the first two terms}\\ \amp = 7(6j) + 6 \amp \text{by the inductive hypothesis}\\ \amp = 6(7j + 1) \amp \text{factor out a 6} \end{align*}$$

Therefore $7^{k+1} - 1$ is a multiple of 6, or in other words, $P(k+1)$ is true. Therefore by the principle of mathematical induction, $P(n)$ is true for all $n \in \N\text{.}$

3

Prove that $1 + 3 + 5 + \cdots + (2n-1) = n^2$ for all $n \ge 1\text{.}$

Solution

Proof

Let $P(n)$ be the statement $1+3 +5 + \cdots + (2n-1) = n^2\text{.}$ We will prove that $P(n)$ is true for all $n \ge 1\text{.}$ First the base case, $P(1)\text{.}$ We have $1 = 1^2$ which is true, so $P(1)$ is established. Now the inductive case. Assume that $P(k)$ is true for some fixed arbitrary $k \ge 1\text{.}$ That is, $1 + 3 + 5 + \cdots + (2k-1) = k^2\text{.}$ We will now prove that $P(k+1)$ is also true (i.e., that $1 + 3 + 5 + \cdots + (2k+1) = (k+1)^2$). We start with the left-hand side of $P(k+1)$ and work to the right-hand side:

$$\begin{align*} 1 + 3 + 5 + \cdots + (2k-1) + (2k+1) ~ \amp = k^2 + (2k+1) \amp \text{by ind. hyp.}\\ \amp = (k+1)^2 \amp \text{by factoring} \end{align*}$$

Thus $P(k+1)$ holds, so by the principle of mathematical induction, $P(n)$ is true for all $n \ge 1\text{.}$

4

Prove that $F_0 + F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1$ where $F_n$ is the $n$th Fibonacci number.

Solution

Proof

Let $P(n)$ be the statement $F_0 + F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1\text{.}$ We will show that $P(n)$ is true for all $n \ge 0\text{.}$ First the base case is easy because $F_0 = 0$ and $F_1 = 1$ so $F_0 = F_1 - 1\text{.}$ Now consider the inductive case. Assume $P(k)$ is true, that is, assume $F_0 + F_2 + F_4 + \cdots + F_{2k} = F_{2k+1} - 1\text{.}$ To establish $P(k+1)$ we work from left to right:

$$\begin{align*} F_0 + F_2 + \cdots + F_{2k} + F_{2k+2} ~ \amp = F_{2k+1} - 1 + F_{2k+2} \amp \text{by ind. hyp.}\\ \amp = F_{2k+1} + F_{2k+2} - 1 \amp\\ \amp = F_{2k+3} - 1 \amp \text{by recursive def.} \end{align*}$$

Therefore $F_0 + F_2 + F_4 + \cdots + F_{2k+2} = F_{2k+3} - 1\text{,}$ which is to say $P(k+1)$ holds. Therefore by the principle of mathematical induction, $P(n)$ is true for all $n \ge 0\text{.}$

5

Prove that $2^n \lt n!$ for all $n \ge 4\text{.}$ (Recall, $n! = 1\cdot 2 \cdot 3 \cdot \cdots\cdot n\text{.}$)

Solution

Proof

Let $P(n)$ be the statement $2^n \lt n!\text{.}$ We will show $P(n)$ is true for all $n \ge 4\text{.}$ First, we check the base case and see that yes, $2^4 \lt 4!$ (as $16 \lt 24$) so $P(4)$ is true. Now for the inductive case. Assume $P(k)$ is true for an arbitrary $k \ge 4\text{.}$ That is, $2^k \lt k!\text{.}$ Now consider $P(k+1)\text{:}$ $2^{k+1} \lt (k+1)!\text{.}$ To prove this, we start with the left side and work to the right side.

$$\begin{align*} 2^{k+1}~ \amp = 2\cdot 2^k \amp\\ \amp \lt 2\cdot k! \amp \text{by the inductive hypothesis}\\ \amp \lt (k+1) \cdot k! \amp \text{ since } k+1 \gt 2\\ \amp = (k+1)! \amp \end{align*}$$

Therefore $2^{k+1} \lt (k+1)!$ so we have established $P(k+1)\text{.}$ Thus by the principle of mathematical induction $P(n)$ is true for all $n \ge 4\text{.}$

6

Prove, by mathematical induction, that $F_0 + F_1 + F_2 + \cdots + F_{n} = F_{n+2} - 1\text{,}$ where $F_n$ is the $n$th Fibonacci number ( $F_0 = 0\text{,}$ $F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$).

7

Zombie Euler and Zombie Cauchy, two famous zombie mathematicians, have just signed up for Twitter accounts. After one day, Zombie Cauchy has more followers than Zombie Euler. Each day after that, the number of new followers of Zombie Cauchy is exactly the same as the number of new followers of Zombie Euler (and neither lose any followers). Explain how a proof by mathematical induction can show that on every day after the first day, Zombie Cauchy will have more followers than Zombie Euler. That is, explain what the base case and inductive case are, and why they together prove that Zombie Cauchy will have more followers on the 4th day.

8

Find the largest number of points which a football team cannot get exactly using just 3-point field goals and 7-point touchdowns (ignore the possibilities of safeties, missed extra points, and two point conversions). Prove your answer is correct by mathematical induction.

9

Prove that the sum of $n$ squares can be found as follows

$$\begin{equation*} 1^2 +2^2 +3^2+...+n^2 = \frac{n(n+1)(2n+1)}{6} \end{equation*}$$

10

What is wrong with the following “proof” of the “fact” that $n+3 = n+7$ for all values of $n$ (besides of course that the thing it is claiming to prove is false)?

Proof

Let $P(n)$ be the statement that $n + 3 = n + 7\text{.}$ We will prove that $P(n)$ is true for all $n \in \N\text{.}$ Assume, for induction that $P(k)$ is true. That is, $k+3 = k+7\text{.}$ We must show that $P(k+1)$ is true. Now since $k + 3 = k + 7\text{,}$ add 1 to both sides. This gives $k + 3 + 1 = k + 7 + 1\text{.}$ Regrouping $(k+1) + 3 = (k+1) + 7\text{.}$ But this is simply $P(k+1)\text{.}$ Thus by the principle of mathematical induction $P(n)$ is true for all $n \in \N\text{.}$

Solution

The only problem is that we never established the base case. Of course, when $n = 0\text{,}$ $0+3 \ne 0+7\text{.}$

11

The proof in the previous problem does not work. But if we modify the “fact,” we can get a working proof. Prove that $n + 3 \lt n + 7$ for all values of $n \in \N\text{.}$ You can do this proof with algebra (without induction), but the goal of this exercise is to write out a valid induction proof.

Answer

Proof

Let $P(n)$ be the statement that $n + 3 \lt n + 7\text{.}$ We will prove that $P(n)$ is true for all $n \in \N\text{.}$ First, note that the base case holds: $0+3 \lt 0+7\text{.}$ Now assume for induction that $P(k)$ is true. That is, $k+3 \lt k+7\text{.}$ We must show that $P(k+1)$ is true. Now since $k + 3 \lt k + 7\text{,}$ add 1 to both sides. This gives $k + 3 + 1 \lt k + 7 + 1\text{.}$ Regrouping $(k+1) + 3 \lt (k+1) + 7\text{.}$ But this is simply $P(k+1)\text{.}$ Thus by the principle of mathematical induction $P(n)$ is true for all $n \in \N\text{.}$

$\square$

12

Find the flaw in the following “proof” of the “fact” that $n \lt 100$ for every $n \in \N\text{.}$

Proof

Let $P(n)$ be the statement $n \lt 100\text{.}$ We will prove $P(n)$ is true for all $n \in \N\text{.}$ First we establish the base case: when $n = 0\text{,}$ $P(n)$ is true, because $0 \lt 100\text{.}$ Now for the inductive step, assume $P(k)$ is true. That is, $k \lt 100\text{.}$ Now if $k \lt 100\text{,}$ then $k$ is some number, like 80. Of course $80+1 = 81$ which is still less than 100. So $k +1 \lt 100$ as well. But this is what $P(k+1)$ claims, so we have shown that $P(k) \imp P(k+1)\text{.}$ Thus by the principle of mathematical induction, $P(n)$ is true for all $n \in \N\text{.}$

Solution

The problem here is that while $P(0)$ is true, and while $P(k) \imp P(k+1)$ for some values of $k\text{,}$ there is at least one value of $k$ (namely $k = 99$) when that implication fails. For a valid proof by induction, $P(k) \imp P(k+1)$ must be true for all values of $k$ greater than or equal to the base case.

13

While the above proof does not work (it better not since the statement it is trying to prove is false!) we can prove something similar. Prove that there is a strictly increasing sequence $a_1, a_2, a_3, \ldots$ of numbers (not necessarily integers) such that $a_n \lt 100$ for all $n \in \N\text{.}$ (By strictly increasing we mean $a_n \lt a_{n+1}$ for all $n\text{.}$ So each term must be larger than the last.)

Solution

Proof

Let $P(n)$ be the statement “there is a strictly increasing sequence $a_1, a_2, \ldots, a_n$ with $a_n \lt 100\text{.}$” We will prove $P(n)$ is true for all $n \ge 1\text{.}$ First we establish the base case: $P(1)$ says there is a single number $a_1$ with $a_1 \lt 100\text{.}$ This is true – take $a_1 = 0\text{.}$ Now for the inductive step, assume $P(k)$ is true. That is there exists a strictly increasing sequence $a_1, a_2, a_3, \ldots, a_k$ with $a_k \lt 100\text{.}$ Now consider this sequence, plus one more term, $a_{k+1}$ which is greater than $a_k$ but less than $100\text{.}$ Such a number exists, for example, the average between $a_k$ and 100. So then $P(k+1)$ is true, so we have shown that $P(k) \imp P(k+1)\text{.}$ Thus by the principle of mathematical induction, $P(n)$ is true for all $n \in \N\text{.}$

14

What is wrong with the following “proof” of the “fact” that for all $n \in \N\text{,}$ the number $n^2 + n$ is odd?

Proof

Let $P(n)$ be the statement “ $n^2 + n$ is odd.” We will prove that $P(n)$ is true for all $n \in \N\text{.}$ Suppose for induction that $P(k)$ is true, that is, that $k^2 + k$ is odd. Now consider the statement $P(k+1)\text{.}$ Now $(k+1)^2 + (k+1) = k^2 + 2k + 1 + k + 1 = k^2 + k + 2k + 2\text{.}$ By the inductive hypothesis, $k^2 + k$ is odd, and of course $2k + 2$ is even. An odd plus an even is always odd, so therefore $(k+1)^2 + (k+1)$ is odd. Therefore by the principle of mathematical induction, $P(n)$ is true for all $n \in \N\text{.}$

$\square$

15

Now give a valid proof (by induction, even though you might be able to do so without using induction) of the statement, “for all $n \in \N\text{,}$ the number $n^2 + n$ is even.”

16

Prove that there is a sequence of positive real numbers $a_0, a_1, a_2, \ldots$ such that the partial sum $a_0 + a_1 + a_2 + \cdots + a_n$ is strictly less than $2$ for all $n \in \N\text{.}$ Hint: think about how you could define what $a_{k+1}$ is to make the induction argument work.

Solution

The idea is to define the sequence so that $a_n$ is less than the distance between the previous partial sum and 2. That way when you add it into the next partial sum, the partial sum is still less than 2. You could do this ahead of time, or use a clever $P(n)$ in the induction proof.

Proof

Let $P(n)$ be the statement, “there is a sequence of positive real numbers $a_0, a_1, a_2, \ldots, a_n$ such that $a_0 + a_1 + a_2 + \cdots + a_n \lt 2\text{.}$”

Base case: Pick any $a_0 \lt 2\text{.}$

Inductive case: Assume that $a_1 + a_2 + \cdots + a_k \lt 2\text{.}$ Now let $a_{k+1} = \frac{2- a_1 + a_2 + \cdots + a_k}{2}\text{.}$ Then $a_1 + a_2 + \cdots +a_k + a_{k+1} \lt 2\text{.}$

Therefore, by the principle of mathematical induction, $P(n)$ is true for all $n \in \N$

17

Prove that every positive integer is either a power of 2, or can be written as the sum of distinct powers of 2.

Solution

The proof will by by strong induction.

Proof

Let $P(n)$ be the statement “$n$ is either a power of 2 or can be written as the sum of distinct powers of 2.” We will show that $P(n)$ is true for all $n \ge 1\text{.}$

Base case: $1 = 2^0$ is a power of 2, so $P(1)$ is true.

Inductive case: Suppose $P(k)$ is true for all $k \lt n\text{.}$ Now if $n$ is a power of 2, we are done. If not, let $2^x$ be the largest power of 2 strictly less than $n\text{.}$ Consider $n - 2^x\text{,}$ which is a smaller number, in fact smaller than both $n$ and $2^x\text{.}$ Thus $n-2^x$ is either a power of 2 or can be written as the sum of distinct powers of 2, but none of them are going to be $2^x\text{,}$ so the together with $2^x$ we have written $n$ as the sum of distinct powers of 2.

Therefore, by the principle of (strong) mathematical induction, $P(n)$ is true for all $n \ge 1\text{.}$

18

Prove, using strong induction, that every natural number is either a Fibonacci number or can be written as the sum of distinct Fibonacci numbers.

19

Use induction to prove that if $n$ people all shake hands with each other, that the total number of handshakes is $\frac{n(n-1)}{2}\text{.}$

Solution

Note, we have already proven this without using induction, but looking at it inductively sheds light onto the problem (and is fun).

Proof

Let $P(n)$ be the statement “when $n$ people shake hands with each other, there are a total of $\frac{n(n-1)}{2}$ handshakes.”

Base case: When $n=2\text{,}$ there will be one handshake, and $\frac{2(2-1)}{2} = 1\text{.}$ Thus $P(2)$ is true.

Inductive case: Assume $P(k)$ is true for arbitrary $k\ge 2$ (that the number of handshakes among $k$ people is $\frac{k(k-1)}{2}\text{.}$ What happens if a $k+1$st person shows up? How many new handshakes take place? The new person must shake hands with everyone there, which is $k$ new handshakes. So the total is now $\frac{k(k-1)}{2} + k = \frac{(k+1)k}{2}\text{,}$ as needed.

Therefore, by the principle of mathematical induction, $P(n)$ is true for all $n \ge 2\text{.}$

20

Suppose that a particular real number $x$ has the property that $x + \frac{1}{x}$ is an integer. Prove that $x^n + \frac{1}{x^n}$ is an integer for all natural numbers $n\text{.}$

Solution

When $n = 0\text{,}$ we get $x^0 +\frac{1}{x^0} = 2$ and when $n = 1\text{,}$ $x + \frac{1}{x}$ is an integer, so the base case holds. Now assume the result holds for all natural numbers $n \lt k\text{.}$ In particular, we know that $x^{k-1} + \frac{1}{x^{k-1}}$ and $x + \frac{1}{x}$ are both integers. Thus their product is also an integer. But,

$$\begin{align*} \left(x^{k-1} + \frac{1}{x^{k-1}}\right)\left(x + \frac{1}{x}\right) \amp = x^k + \frac{x^{k-1}}{x} + \frac{x}{x^{k-1}} + \frac{1}{x^k}\\ \amp = x^k + \frac{1}{x^k} + x^{k-2} + \frac{1}{x^{k-2}} \end{align*}$$

Note also that $x^{k-2} + \frac{1}{x^{k-2}}$ is an integer by the induction hypothesis, so we can conclude that $x^k + \frac{1}{x^k}$ is an integer.

21

Use induction to prove that $\d\sum_{k=0}^n {n \choose k} = 2^n\text{.}$ That is, the sum of the $n$th row of Pascal's Triangle is $2^n\text{.}$

22

Use induction to prove ${4 \choose 0} + {5 \choose 1} + {6 \choose 2} + \cdots + {4+n \choose n} = {5+n \choose n}\text{.}$ (This is an example of the hockey stick theorem.)

23

Use the product rule for logarithms ( $\log(ab) = \log(a) + \log(b)$) to prove, by induction on $n\text{,}$ that $\log(a^n) = n \log(a)\text{,}$ for all natural numbers $n \ge 2\text{.}$

Solution

The idea here is that if we take the logarithm of $a^n\text{,}$ we can increase $n$ by 1 if we multiply by another $a$ (inside the logarithm). This results in adding 1 more $\log(a)$ to the total.

Proof

Let $P(n)$ be the statement $\log(a^n) = n \log(a)\text{.}$ The base case, $P(2)$ is true, because $\log(a^2) = \log(a\cdot a) = \log(a) + \log(a) = 2\log(a)\text{,}$ by the product rule for logarithms. Now assume, for induction, that $P(k)$ is true. That is, $\log(a^k) = k\log(a)\text{.}$ Consider $\log(a^{k+1})\text{.}$ We have

$$\begin{equation*} \log(a^{k+1}) = \log(a^k\cdot a) = \log(a^k) + \log(a) = k\log(a) + \log(a) \end{equation*}$$

with the last equality due to the inductive hypothesis. But this simplifies to $(k+1) \log(a)\text{,}$ establishing $P(k+1)\text{.}$ Therefore by the principle of mathematical induction, $P(n)$ is true for all $n \ge 2\text{.}$

24

Let $f_1, f_2,\ldots, f_n$ be differentiable functions. Prove, using induction, that

$$\begin{equation*} (f_1 + f_2 + \cdots + f_n)' = f_1' + f_2' + \cdots + f_n' \end{equation*}$$

You may assume $(f+g)' = f' + g'$ for any differentiable functions $f$ and $g\text{.}$

Hint

You are allowed to assume the base case. For the inductive case, group all but the last function together as one sum of functions, then apply the usual sum of derivatives rule, and then the inductive hypothesis.

25

Suppose $f_1, f_2, \ldots, f_n$ are differentiable functions. Use mathematical induction to prove the generalized product rule:

$$\begin{equation*} (f_1 f_2 f_3 \cdots f_n)' = f_1' f_2 f_3 \cdots f_n + f_1 f_2' f_3 \cdots f_n + f_1 f_2 f_3' \cdots f_n + \cdots + f_1 f_2 f_3 \cdots f_n' \end{equation*}$$

You may assume the product rule for two functions is true.

Hint

For the inductive step, we know by the product rule for two functions that

$$\begin{equation*} (f_1f_2f_3 \cdots f_k f_{k+1})' = (f_1f_2f_3\cdots f_k)'f_{k+1} + (f_1f_2f_3\cdots f_k)f_{k+1}' \end{equation*}$$

Then use the inductive hypothesis on the first summand, and distribute.