2_1_3A_Definitions

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/2%3A_Sequences/2.1%3A_Definitions

\\ \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}{&}\\

Investigate!

What comes next:

\begin{equation\*} 1, \~~11, \~~21, \~~1211, \~~111221, \~~312211, \~~\ldots \end{equation\*}

A sequence is simply an ordered list of numbers. For example, here is a sequence: 0, 1, 2, 3, 4, 5, …. This is different from the set \\\N\\ because, while the sequence is a complete list of every element in the set of natural numbers, in the sequence we very much care what order the numbers come in. For this reason, when we use variables to represent terms in a sequence they will look like this:

\begin{equation\*} a_0, a_1, a_2, a_3, \ldots \end{equation\*}

To refer to the *entire* sequence at once, we will write \$a_n)\_{n\in\N}\\ or \$a_n)\_{n\ge 0}\text{,}\\ or sometimes if we are being sloppy, just \$a_n)\\ (in which case we assume we start the sequence with \\a_0\$.

We might replace the \\a\\ with another letter, and sometimes we omit \\a_0\text{,}\\ starting with \\a_1\text{,}\\ in which case we would use \$a_n)\_{n \ge 1}\\ to refer to the sequence as a whole. The numbers in the subscripts are called indices (the plural of index ).

While we often just think of sequences as an ordered list of numbers, they really are a type of function. Specifically, the sequence \$a_n)\_{n\ge 0}\\ is a function with domain \\\N\\ where \\a_n\\ is the image of the natural number \\n\text{.}\\ Later we will manipulate sequences in much the same way you have manipulated functions in algebra or calculus. We can shift a sequence up or down, add two sequences, or ask for the rate of change of a sequence. These are done exactly as you would for functions.

That said, while keeping the rigorous mathematical definition in mind is helpful, we often describe sequences by writing out the first few terms.

Example \\\PageIndex{1}\\

Can you find the next term in the following sequences?

1. \\7,7,7,7,7, \ldots\\

2. \\3, -3, 3, -3, 3, \ldots\\

3. \\1, 5, 2, 10, 3, 15, \ldots\\

4. \\1, 2, 4, 8, 16, 32, \ldots\\

5. \\1, 4, 9, 16, 25, 36, \ldots\\

6. \\1, 2, 3, 5, 8, 13, 21, \ldots\\

7. \\1, 3, 6, 10, 15, 21, \ldots\\

8. \\2, 3, 5, 7, 11, 13, \ldots\\

9. \\3, 2, 1, 0, -1, \ldots\\

10. \\1, 1, 2, 6, \ldots\\

Solution

No you cannot. You might guess that the next terms are:

1. \\7\\

2. \\-3\\

3. \\4\\

4. 64

5. 49

6. 34

7. 28

8. 17

9. \\-2\\

10. \\24\\

In fact, those are the next terms of the sequences I had in mind when I made up the example, but there is no way to be sure they are correct.

Still, we will often do this. Given the first few terms of a sequence, we can ask what the pattern in the sequence suggests the next terms are.

Given that no number of initial terms in a sequence is enough to say for certain which sequence we are dealing with, we need to find another way to specify a sequence. We consider two ways to do this:

Closed formula

A closed formula for a sequence \$a_n)\_{n\in\N}\\ is a formula for \\a_n\\ using a fixed finite number of operations on \\n\text{.}\\ This is what you normally think of as a formula in \\n\text{,}\\ just like if you were defining a function in terms of \\n\\ (because that is exactly what you are doing).

Recursive definition

A recursive definition (sometimes called an inductive definition ) for a sequence \$a_n)\_{n\in\N}\\ consists of a recurrence relation : an equation relating a term of the sequence to previous terms (terms with smaller index) and an initial condition : a list of a few terms of the sequence (one less than the number of terms in the recurrence relation).

It is easier to understand what is going on here with an example:

Example \\\PageIndex{2}\\

Here are a few closed formulas for sequences:

\\a_n = n^2\text{.}\\
\\\d a_n = \frac{n(n+1)}{2}\text{.}\\
\\\d a_n = \frac{\left(\frac{1 + \sqrt 5}{2}\right)^n - \left(\frac{1 + \sqrt 5}{2}\right)^{-n}}{5}\text{.}\\

Note in each case, if you are given \\n\text{,}\\ you can calculate \\a_n\\ directly: just plug in \\n\text{.}\\ For example, to find \\a_3\\ in the second sequence, just compute \\a_3 = \frac{3(3+1)}{2} = 6\text{.}\\

Here are a few recursive definitions for sequences:

\\a_n = 2a\_{n-1}\\ with \\a_0 = 1\text{.}\\
\\a_n = 2a\_{n-1}\\ with \\a_0 = 27\text{.}\\
\\a_n = a\_{n-1} + a\_{n-2}\\ with \\a_0 = 0\\ and \\a_1 = 1\text{.}\\

In these cases, if you are given \\n\text{,}\\ you cannot calculate \\a_n\\ directly, you first need to find \\a\_{n-1}\\ (or \\a\_{n-1}\\ and \\a\_{n-2}\$. In the second sequence, to find \\a_3\\ you would take \\2a_2\text{,}\\ but to find \\a_2 = 2a_1\\ we would need to know \\a_1 = 2a_0\text{.}\\ We do know this, so we could trace back through these equations to find \\a_1 = 54\text{,}\\ \\a_2 = 108\\ and finally \\a_3 = 216\text{.}\\

Investigate!

You have a large collection of \\1\times 1\\ squares and \\1\times 2\\ dominoes. You want to arrange these to make a \\1 \times 15\\ strip. How many ways can you do this?

1. Start by collecting data. How many length \\1\times 1\\ strips can you make? How many \\1\times 2\\ strips? How many \\1\times 3\\ strips? And so on.

2. How are the \\1\times 3\\ and \\1 \times 4\\ strips related to the \\1\times 5\\ strips?

3. How many \\1\times 15\\ strips can you make?

4. What if I asked you to find the number of \\1\times 1000\\ strips? Would the method you used to calculate the number fo \\1 \times 15\\ strips be helpful?

You might wonder why we would bother with recursive definitions for sequences. After all, it is harder to find \\a_n\\ with a recursive definition than with a closed formula. This is true, but it is also harder to find a closed formula for a sequence than it is to find a recursive definition. So to find a useful closed formula, we might first find the recursive definition, then use that to find the closed formula.

This is not to say that recursive definitions aren't useful in finding \\a_n\text{.}\\ You can always calculate \\a_n\\ given a recursive definition, it might just take a while.

Example \\\PageIndex{3}\\

Find \\a_6\\ in the sequence defined by \\a_n = 2a\_{n-1} - a\_{n-2}\\ with \\a_0 = 3\\ and \\a_1 = 4\text{.}\\

Solution

We know that \\a_6 = 2a_5 - a_4\text{.}\\ So to find \\a_6\\ we need to find \\a_5\\ and \\a_4\text{.}\\ Well

\begin{equation\*} a_5 = 2a_4 - a_3 \qquad \text{and} \qquad a_4 = 2a_3 - a_2, \end{equation\*}

so if we can only find \\a_3\\ and \\a_2\\ we would be set. Of course

\begin{equation\*} a_3 = 2a_2 - a_1 \qquad \text{and} \qquad a_2 = 2a_1 - a_0, \end{equation\*}

so we only need to find \\a_1\\ and \\a_0\text{.}\\ But we are given these. Thus

\begin{align\*} a_0 & = 3\\ a_1 & = 4\\ a_2 & = 2\cdot 4 - 3 = 5\\ a_3 & = 2\cdot 5 - 4 = 6\\ a_4 & = 2\cdot 6 - 5 = 7\\ a_5 & = 2\cdot 7 - 6 = 8\\ a_6 & = 2\cdot 8 - 7 = 9. \end{align\*}

Note that now we can guess a closed formula for the \\n\\th term of the sequence: \\a_n = n+3\text{.}\\ To be sure this will always work, we could plug in this formula into the recurrence relation:

\begin{align\*} 2a\_{n-1} - a\_{n-2} & = 2((n-1) + 3) - ((n-2) + 3)\\ & = 2n + 4 - n - 1 \\ & = n + 3\\ & = a_n. \end{align\*}

That is not quite enough though, since there can be multiple closed formulas that satisfy the same recurrence relation; we must also check that our closed formula agrees on the initial terms of the sequence. Since \\a_0 = 0 + 3 = 3\\ and \\a_1 = 1+3 = 4\\ are the correct initial conditions, we can now conclude we have the correct closed formula.

Finding closed formulas, or even recursive definitions, for sequences is not trivial. There is no one method for doing this. Just like in evaluating integrals or solving differential equations, it is useful to have a bag of tricks you can apply, but sometimes there is no easy answer.

One useful method is to relate a given sequence to another sequence for which we already know the closed formula.

Example \\\PageIndex{4}\\

Use the formulas \\T_n = \frac{n(n+1)}{2}\\ and \\a_n = 2^n\\ to find closed formulas for the following sequences.

1. \$b_n)\text{:}\\ \\1, 2, 4, 7, 11, 16, 22, \ldots \text{.}\\

2. \$c_n)\text{:}\\ \\3, 5, 9, 17, 33,\ldots \text{.}\\

3. \$d_n)\text{:}\\ \\0, 2, 6, 12, 20, 30, 42,\ldots \text{.}\\

4. \$e_n)\text{:}\\ \\3, 6, 10, 15, 21, 28, \ldots\text{.}\\

5. \$f_n)\text{:}\\ \\0, 1, 3, 7, 15, 31, \ldots \text{.}\\

6. \$g_n)\\ \\3, 6, 12, 24, 48, \ldots \text{.}\\

7. \$h_n)\text{:}\\ \\6, 10, 18, 34, 66, \ldots \text{.}\\

8. \$j_n)\text{:}\\ \\15, 33, 57, 87, 123, \ldots\text{.}\\

Solution

1. Before you say this is impossible, what we are asking for is simply to find a closed formula which agrees with all of the initial terms of the sequences. Of course there is no way to read into the mind of the person who wrote the numbers down, but we can at least do this.

2. The first few terms of \$T_n)\_{n\ge 0}\\ are \\0, 1, 3, 6, 10, 15, 21, \ldots\\ (these are called the triangular numbers ). The first few terms of \$a_n)\_{n\ge 0}\\ are \\1, 2, 4, 8, 16, \ldots\text{.}\\ Let's try to find formulas for the given sequences:

3. \$1, 2, 4, 7, 11, 16, 22, \ldots)\text{.}\\ Note that if subtract 1 from each term, we get the sequence \$T_n)\text{.}\\ So we have \\b_n = T_n + 1\text{.}\\ Therefore a closed formula is \\b_n = \frac{n(n+1)}{2} + 1\text{.}\\ A quick check of the first few \\n\\ confirms we have it right.

4. \$3, 5, 9, 17, 33, \ldots )\text{.}\\ Each term in this sequence is one more than a power of 2, so we might guess the closed formula is \\c_n = a_n+1 = 2^n + 1\text{.}\\ If we try this though, we get \\c_0 2^0 + 1 = 2\\ and \\c_1 = 2^1 + 1 = 3\text{.}\\ We are off because the indices are shifted. What we really want is \\c_n = a\_{n+1}+1\\ giving \\c_n = 2^{n+1} + 1\text{.}\\

5. (\\0, 2, 6, 12, 20, 30, 42,\ldots \$. Notice that all these terms are even. What happens if we factor out a 2? We get \$T_n)\text{!}\\ More precisely, we find that \\d_n/2 = T_n\text{,}\\ so this sequence has closed formula \\d_n = n(n+1)\text{.}\\

6. \$3, 6, 10, 15, 21, 28, \ldots)\text{.}\\ These are all triangular numbers. However, we are starting with 3 as our initial term instead of as our third term. So if we could plug in 2 instead of 0 into the formula for \\T_n\text{,}\\ we would be set. Therefore the closed formula is \\e_n = \frac{(n+2)(n+3)}{2}\\ (where \\n+3\\ came from \$n+2)+1\$. Thinking about sequences as functions, we are doing a horizontal shift by 2: \\e_n = T\_{n+2}\\ which would cause the graph to shift 2 units to the left.

7. \$0, 1, 3, 7, 15, 31, \ldots )\text{.}\\ Try adding 1 to each term and we get powers of 2. You might guess this because each term is a little more than twice the previous term (the powers of 2 are *exactly* twice the previous term). Closed formula: \\f_n = 2^{n} - 1\text{.}\\

8. \$3, 6, 12, 24, 48, \ldots )\text{.}\\ These numbers are also doubling each time, but are also all multiples of 3. Dividing each by 3 gives 1, 2, 4, 8, …. Aha. We get the closed formula \\g_n = 3\cdot 2^{n}\text{.}\\

9. \$6, 10, 18, 34, 66, \ldots )\text{.}\\ To get from one term to the next, we almost double each term. So maybe we can relate this back to \\2^n\text{.}\\ Yes, each term is 2 more than a power of 2. So we get \\h_n = 2^{n+2} + 2\\ (the \\n+2\\ is because the first term is 2 more than \\2^2\text{,}\\ not \\2^0\$. Alternatively, we could have related this sequence to the second sequence in this example: starting with 3, 5, 9, 17, … we see that this sequence is twice the terms from that sequence. That sequence had closed formula \\c_n = 2^{n+1} + 1\text{.}\\ Our sequence here would be twice this, so \\h_n = 2(2^n + 1)\text{,}\\ which is the same as we got before.

10. \$15, 33, 57, 87, 123, \ldots)\text{.}\\ Try dividing each term by 3. That gives the sequence \\5, 11, 19, 29, 41,\ldots\text{.}\\ Now add 1: \\6, 12, 20, 30, 42, \ldots\text{,}\\ which is \$d_n)\\ in this example, except starting with 6 instead of 0. So let's start with the formula \\d_n= n(n+1)\text{.}\\ To start with the 6, we shift: \$n+2)(n+3)\text{.}\\ But this is one too many, so subtract 1: \$n+2)(n+3) - 1\text{.}\\ That gives us our sequence, but divided by 3. So we want \\j_n = 3((n+2)(n+3) - 1)\text{.}\\

---

2_2_3A_Arithmetic_and_Geometric_Sequences

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/2%3A_Sequences/2.2%3A_Arithmetic_and_Geometric_Sequences

\\ \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}{&}\\

Investigate!

For the patterns of dots below, draw the next pattern in the sequence. Then give a recursive definition and a closed formula for the number of dots in the \\n\\th pattern.

1. \![inv_dots-seq1.svg$$(https://math.libretexts.org/@api/deki/files/12890/inv_dots-seq1.svg?revision=1&size=bestfit&width=334&height=80)

2. \![inv_dots-seq2.svg$$(https://math.libretexts.org/@api/deki/files/12892/inv_dots-seq2.svg?revision=1&size=bestfit&width=336&height=164)

3. \![inv_dots-seq3.svg$$(https://math.libretexts.org/@api/deki/files/12891/inv_dots-seq3.svg?revision=1&size=bestfit&width=375&height=91)

\![$$(https://math.libretexts.org/images/inv_dots-seq1.svg)

We now turn to the question of finding closed formulas for particular types of sequences.

Arithmetic Sequences

If the terms of a sequence differ by a constant, we say the sequence is arithmetic . If the initial term (\\a_0\$ of the sequence is \\a\\ and the common difference is \\d\text{,}\\ then we have,

Recursive definition: \\a_n = a\_{n-1} + d\\ with \\a_0 = a\text{.}\\

Closed formula: \\a_n = a + dn\text{.}\\

How do we know this? For the recursive definition, we need to specify \\a_0\text{.}\\ Then we need to express \\a_n\\ in terms of \\a\_{n-1}\text{.}\\ If we call the first term \\a\text{,}\\ then \\a_0 = a\text{.}\\ For the recurrence relation, by the definition of an arithmetic sequence, the difference between successive terms is some constant, say \\d\text{.}\\ So \\a_n - a\_{n-1} = d\text{,}\\ or in other words,

\begin{equation\*} a_0 = a \qquad a_n=a\_{n-1}+d. \end{equation\*}

To find a closed formula, first write out the sequence in general:

\begin{align\*} a_0 & = a\\ a_1 & = a_0 + d = a+d\\ a_2 & = a_1 + d = a+d+d = a+2d\\ a_3 & = a_2 + d = a+2d+d = a+3d\\ & \vdots \end{align\*}

We see that to find the \\n\\th term, we need to start with \\a\\ and then add \\d\\ a bunch of times. In fact, add it \\n\\ times. Thus \\a_n = a+dn\text{.}\\

Example \\\PageIndex{1}\\

Find recursive definitions and closed formulas for the sequences below. Assume the first term listed is \\a_0\text{.}\\

1. \\2, 5, 8, 11, 14, \ldots\text{.}\\

2. \\50, 43, 36, 29, \ldots\text{.}\\

Solution

First we should check that these sequences really are arithmetic by taking differences of successive terms. Doing so will reveal the common difference \\d\text{.}\\

1. \\5-2 = 3\text{,}\\ \\8-5 = 3\text{,}\\ etc. To get from each term to the next, we add three, so \\d = 3\text{.}\\ The recursive definition is therefore \\a_n = a\_{n-1} + 3\\ with \\a_0 = 2\text{.}\\ The closed formula is \\a_n = 2 + 3n\text{.}\\

2. Here the common difference is \\-7\text{,}\\ since we add \\-7\\ to 50 to get 43, and so on. Thus we have a recursive definition of \\a_n = a\_{n-1} - 7\\ with \\a_0 = 50\text{.}\\ The closed formula is \\a_n = 50 - 7n\text{.}\\

What about sequences like \\2, 6, 18, 54, \ldots\text{?}\\ This is not arithmetic because the difference between terms is not constant. However, the *ratio* between successive terms is constant. We call such sequences geometric .

The recursive definition for the geometric sequence with initial term \\a\\ and common ratio \\r\\ is \\a_n = a\_{n}\cdot r; a_0 = a\text{.}\\ To get the next term we multiply the previous term by \\r\text{.}\\ We can find the closed formula like we did for the arithmetic progression. Write

\begin{align\*} a_0 & = a\\ a_1 & = a_0\cdot r\\ a_2 & = a_1 \cdot r = a_0\cdot r\cdot r = a_0\cdot r^2\\ & \vdots \end{align\*}

We must multiply the first term \\a\\ by \\r\\ a number of times, \\n\\ times to be precise. We get \\a_n = a\cdot r^{n}\text{.}\\

Geometric Sequences

A sequence is called geometric if the ratio between successive terms is constant. Suppose the initial term \\a_0\\ is \\a\\ and the common ratio is \\r\text{.}\\ Then we have,

Recursive definition: \\a_n = ra\_{n-1}\\ with \\a_0 = a\text{.}\\
Closed formula: \\a_n = a\cdot r^{n}\text{.}\\

Example \\\PageIndex{3}\\

Find the recursive and closed formula for the sequences below. Again, the first term listed is \\a_0\text{.}\\

1. \\3, 6, 12, 24, 48, \ldots\\

2. \\27, 9, 3, 1, 1/3, \ldots\\

Solution

Again, we should first check that these sequences really are geometric, this time by dividing each term by its previous term. Assuming this ratio is constant, we will have found \\r\text{.}\\

1. \\6/3 = 2\text{,}\\ \\12/6 = 2\text{,}\\ \\24/12 = 2\text{,}\\ etc. Yes, to get from any term to the next, we multiply by \\r = 2\text{.}\\ So the recursive definition is \\a_n = 2a\_{n-1}\\ with \\a_0 = 3\text{.}\\ The closed formula is \\a_n = 3\cdot 2^{n}\text{.}\\

2. The common ratio is \\r = 1/3\text{.}\\ So the sequence has recursive definition \\a_n = \frac{1}{3}a\_{n-1}\\ with \\a_0 = 27\\ and closed formula \\a_n = 27\cdot \frac{1}{3}^{n}\text{.}\\

In the examples and formulas above, we assumed that the *initial* term was \\a_0\text{.}\\ If your sequence starts with \\a_1\text{,}\\ you can easily find the term that would have been \\a_0\\ and use that in the formula. For example, if we want a formula for the sequence \\2, 5, 8,\ldots\\ and insist that \\2= a_1\text{,}\\ then we can find \\a_0 = -1\\ (since the sequence is arithmetic with common difference 3, we have \\a_0 + 3 = a_1\$. Then the closed formula will be \\a_n = -1 + 3n\text{.}\\

If you look at other textbooks or online, you might find that their closed formulas for arithmetic and geometric sequences differ from ours. Specifically, you might find the formulas \\a_n = a +(n-1)d\\ (arithmetic) and \\a_n = a\cdot r^{n-1}\\ (geometric). Which is correct? Both! In our case, we take \\a\\ to be \\a_0\text{.}\\ If instead we had \\a_1\\ as our initial term, we would get the (slightly more complicated) formulas you find elsewhere.

Sums of Arithmetic and Geometric Sequences

Investigate!

Your neighborhood grocery store has a candy machine full of Skittles.

1. Suppose that the candy machine currently holds exactly 650 Skittles, and every time someone inserts a quarter, exactly 7 Skittles come out of the machine.

1. How many Skittles will be left in the machine after 20 quarters have been inserted?

2. Will there ever be exactly zero Skittles left in the machine? Explain.

2. What if the candy machine gives 7 Skittles to the first customer who put in a quarter, 10 to the second, 13 to the third, 16 to the fourth, etc. How many Skittles has the machine given out after 20 quarters are put into the machine?

3. Now, what if the machine gives 4 Skittles to the first customer, 7 to the second, 12 to the third, 19 to the fourth, etc. How many Skittles has the machine given out after 20 quarters are put into the machine?

Look at the sequence \$T_n)\_{n\ge 1}\\ which starts \\1, 3, 6, 10, 15,\ldots\text{.}\\ These are called the triangular numbers since they represent the number of dots in an equilateral triangle (think of how you arrange 10 bowling pins: a row of 4 plus a row of 3 plus a row of 2 and a row of 1).

\![$$(https://math.libretexts.org/images/image-46.svg)

Is this sequence arithmetic? No, since \\3-1 = 2\\ and \\6-3 = 3 \ne 2\text{,}\\ so there is no common difference. Is the sequence geometric? No. \\3/1 = 3\\ but \\6/3 = 2\text{,}\\ so there is no common ratio. What to do?

Notice that the differences between terms form an arithmetic sequence: \\2, 3, 4, 5, 6,\ldots\text{.}\\ This says that the \\n\\th term of the sequence \\1,3,6,10,15,\ldots\\ is the *sum* of the first \\n\\ terms in the sequence \\1,2,3,4,5,\ldots\text{.}\\ We say that the first sequence is the sequence of partial sums of the second sequence (partial sums because we are not taking the sum of all infinitely many terms). If we know how to add up the terms of an arithmetic sequence, we could use this to find a closed formula for a sequence whose differences are the terms of that arithmetic sequence.

This should become clearer if we write the triangular numbers like this:

\begin{align\*} 1 & = 1\\ 3 & = 1+2\\ 6 & = 1 + 2 + 3\\ 10 & = 1+2 + 3+ 4\\ \vdots & \qquad \vdots\\ T_n & = 1 + 2 + 3 + \cdots + n. \end{align\*}

Consider how we could find the sum of the first 100 positive integers (that is, \\T\_{100}\$. Instead of adding them in order, we regroup and add \\1+100 = 101\text{.}\\ The next pair to combine is \\2+99 = 101\text{.}\\ Then \\3+98 = 101\text{.}\\ Keep going. This gives 50 pairs which each add up to \\101\text{,}\\ so \\T\_{100} = 101\cdot 50 = 5050\text{.}\\¹This insight is usually attributed to Carl Friedrich Gauss, one of the greatest mathematicians of all time, who discovered it as a child when his unpleasant elementary teacher thought he would keep the class busy by requiring them to compute the lengthy sum.

In general, using this same sort of regrouping, we find that \\T_n = \frac{n(n+1)}{2}\text{.}\\ Incidentally, this is exactly the same as \\{n+1 \choose 2}\text{,}\\ which makes sense if you think of the triangular numbers as counting the number of handshakes that take place at a party with \\n+1\\ people: the first person shakes \\n\\ hands, the next shakes an additional \\n-1\\ hands and so on.

The point of all of this is that some sequences, while not arithmetic or geometric, can be interpreted as the sequence of partial sums of arithmetic and geometric sequences. Luckily there are methods we can use to compute these sums quickly.

Summing Arithmetic Sequences: Reverse and Add

Here is a technique that allows us to quickly find the sum of an arithmetic sequence.

Example \\\PageIndex{4}\\

Find the sum: \\2 + 5 + 8 + 11 + 14 + \cdots + 470\text{.}\\

Solution

The idea is to mimic how we found the formula for triangular numbers. If we add the first and last terms, we get 472. The second term and second-to-last term also add up to 472. To keep track of everything, we might express this as follows. Call the sum \\S\text{.}\\ Then,

| | | | | | | | | | |

|-----------------|---------|-------|---------|-------|---------|----------------|---------|-------|---------|

| \\S =\\ | \\2\\ | \\+\\ | \\5\\ | \\+\\ | \\8\\ | \\+ \cdots +\\ | \\467\\ | \\+\\ | 470 |

| \\+ \quad S =\\ | \\470\\ | \\+\\ | \\467\\ | \\+\\ | \\464\\ | \\+ \cdots +\\ | \\5\\ | \\+\\ | 2 |

| \\2S =\\ | \\472\\ | \\+\\ | \\472\\ | \\+\\ | \\472\\ | \\+ \cdots +\\ | \\472\\ | \\+\\ | \\472\\ |

To find \\2S\\ then we add 472 to itself a number of times. What number? We need to decide how many terms ( summands ) are in the sum. Since the terms form an arithmetic sequence, the \\n\\th term in the sum (counting \\2\\ as the 0th term) can be expressed as \\2 + 3n\text{.}\\ If \\2 + 3n = 470\\ then \\n = 156\text{.}\\ So \\n\\ ranges from 0 to 156, giving 157 terms in the sum. This is the number of 472's in the sum for \\2S\text{.}\\ Thus

\begin{equation\*} 2S = 157\cdot 472 = 74104 \end{equation\*}

It is now easy to find \\S\text{:}\\

\begin{equation\*} S = 74104/2 = 37052 \end{equation\*}

This will work for any sum of *arithmetic* sequences. Call the sum \\S\text{.}\\ Reverse and add. This produces a single number added to itself many times. Find the number of times. Multiply. Divide by 2. Done.

Example \\\PageIndex{5}\\

Find a closed formula for \\6 + 10 + 14 + \cdots + (4n - 2)\text{.}\\

Solution

Again, we have a sum of an arithmetic sequence. We need to know how many terms are in the sequence. Clearly each term in the sequence has the form \\4k -2\\ (as evidenced by the last term). For which values of \\k\\ though? To get 6, \\k = 2\text{.}\\ To get \\4n-2\\ take \\k = n\text{.}\\ So to find the number of terms, we need to know how many integers are in the range \\2,3,\ldots, n\text{.}\\ The answer is \\n-1\text{.}\\ (There are \\n\\ numbers from 1 to \\n\text{,}\\ so one less if we start with 2.)

Now reverse and add:

| | | | | | | | |

|-----------------|----------|-------|----------|----------------|----------|-------|----------|

| \\S =\\ | \\6\\ | \\+\\ | \\10\\ | \\+ \cdots +\\ | \\4n-6\\ | \\+\\ | \\4n-2\\ |

| \\+ \quad S =\\ | \\4n-2\\ | \\+\\ | \\4n-6\\ | \\+ \cdots +\\ | \\10\\ | \\+\\ | 6 |

| \\2S =\\ | \\4n+4\\ | \\+\\ | \\4n+4\\ | \\+ \cdots +\\ | \\4n+4\\ | \\+\\ | \\4n+4\\ |

Since there are \\n-2\\ terms, we get

\begin{equation\*} 2S = (n-2)(4n+4)\qquad \mbox{ so } \qquad S = \frac{(n-2)(4n+4)}{2} \end{equation\*}

Besides finding sums, we can use this technique to find closed formulas for sequences we recognize as sequences of partial sums.

Example \\\PageIndex{6}\\

Use partial sums to find a closed formula for \$a_n)\_{n\ge 0}\\ which starts \\2, 3, 7, 14, 24, 37,\ldots \ldots\\

Solution

First, if you look at the differences between terms, you get a sequence of differences: \\1,4,7,10,13, \ldots\text{,}\\ which is an arithmetic sequence. Written another way:

\begin{align\*} a_0 & = 2\\ a_1 & = 2+1\\ a_2 & = 2+1+4\\ a_3 & = 2+1+4+7 \end{align\*}

and so on. We can write the general term of \$a_n)\\ in terms of the arithmetic sequence as follows:

\begin{equation\*} a_n = 2 + 1 + 4 + 7 + 10 + \cdots + (1+3(n-1)) \end{equation\*}

(we use \\1+3(n-1)\\ instead of \\1+3n\\ to get the indices to line up correctly; for \\a_3\\ we add up to 7, which is \\1+3(3-1)\$.

We can reverse and add, but the initial 2 does not fit our pattern. This just means we need to keep the 2 out of the reverse part:

| | | | | | | | |

|---------------|-------|-------|--------------|-------|--------------|----------------|--------------|

| \\a_n =\\ | \\2\\ | \\+\\ | \\1\\ | \\+\\ | \\4\\ | \\+ \cdots +\\ | \\1+3(n-1)\\ |

| \\+ ~ a_n =\\ | \\2\\ | \\+\\ | \\1+3(n-1)\\ | \\+\\ | \\1+3(n-2)\\ | \\+ \cdots +\\ | \\1\\ |

| \\2a_n =\\ | \\4\\ | \\+\\ | \\2+3(n-1)\\ | \\+\\ | \\2+3(n-1)\\ | \\+ \cdots +\\ | \\2+3(n-1)\\ |

Not counting the first term (the 4) there are \\n\\ summands of \\2+3(n-1) = 3n-1\\ so the right-hand side becomes \\2+(3n-1)n\text{.}\\

Finally, solving for \\a_n\\ we get

\begin{equation\*} a_n = \d \frac{4+(3n-1)n}{2}. \end{equation\*}

Just to be sure, we check \\a_0 = \frac{4}{2} = 2\text{,}\\ \\a_1 = \frac{4+2}{2} = 3\text{,}\\ etc. We have the correct closed formula.

Summing Geometric Sequences: Multiply, Shift and Subtract

To find the sum of a geometric sequence, we cannot just reverse and add. Do you see why? The reason we got the same term added to itself many times is because there was a constant difference. So as we added that difference in one direction, we subtracted the difference going the other way, leaving a constant total. For geometric sums, we have a different technique.

Example \\\PageIndex{7}\\

What is \\3 + 6 + 12 + 24 + \cdots + 12288\text{?}\\

Solution

Multiply each term by 2, the common ratio. You get \\2S = 6 + 12 + 24 + \cdots + 24576\\. Now subtract: \\2S - S = -3 + 24576 = 24573\text{.}\\ Since \\2S - S = S\text{,}\\ we have our answer.

To better see what happened in the above example, try writing it this way:

| | | | |

|-----------|------------|----------------------------------|-------------|

| \\S=\\ | \\3 \\ +\\ | \\6 + 12 + 24 + \cdots + 12288\\ | |

| \\-~2S=\\ | | \\6 + 12 + 24 + \cdots + 12288\\ | \\+ 24576\\ |

| \\-S = \\ | \\3 \\ +\\ | \\0 + 0 + 0 + \cdots + 0 \\ | \\-24576\\ |

Then divide both sides by \\-1\\ and we have the same result for \\S\text{.}\\ The idea is, by multiplying the sum by the common ratio, each term becomes the next term. We shift over the sum to get the subtraction to mostly cancel out, leaving just the first term and new last term.

Example \\\PageIndex{8}\\

Find a closed formula for \\S(n) = 2 + 10 + 50 + \cdots + 2\cdot 5^n\text{.}\\

Solution

The common ratio is 5. So we have

| | |

|------------|----------------------------------------------------------------|

| \\S\\ | \\= 2 + 10 + 50 + \cdots + 2\cdot 5^n\\ |

| \\-\~~5S\\ | \\= \~\~\~\~\~~10 + 50 + \cdots + 2\cdot 5^n + 2\cdot5^{n+1}\\ |

| \\-4S\\ | \\= 2 - 2\cdot5^{n+1}\\ |

Thus \\S = \dfrac{2-2\cdot 5^{n+1}}{-4}\\

Even though this might seem like a new technique, you have probably used it before.

Example \\\PageIndex{9}\\

Express \\0.464646\ldots\\ as a fraction.

Solution

Let \\N = 0.46464646\ldots\text{.}\\ Consider \\0.01N\text{.}\\ We get:

| | | |

|-------|-------------|----------------------|

| | \\N =\\ | \\0.4646464\ldots\\ |

| \\-\\ | \\0.01N =\\ | \\0.00464646\ldots\\ |

| | \\0.99N =\\ | \\0.46\\ |

So \\N = \frac{46}{99}\text{.}\\ What have we done? We viewed the repeating decimal \\0.464646\ldots\\ as a sum of the geometric sequence \\0.46, 0.0046, 0.000046, \ldots\\ The common ratio is \\0.01\text{.}\\ The only real difference is that we are now computing an *infinite* geometric sum, we do not have the extra “last” term to consider. Really, this is the result of taking a limit as you would in calculus when you compute *infinite* geometric sums.

\\\sum\\ and \\\prod\\ notation

To simplify writing out sums, we will use notation like \\\d\sum\_{k=1}^n a_k\text{.}\\ This means add up the \\a_k\\'s where \\k\\ changes from 1 to \\n\text{.}\\

Example \\\PageIndex{10}\\

Use \\\sum\\ notation to rewrite the sums:

1. \\1 + 2 + 3 + 4 + \cdots + 100\\

2. \\1 + 2 + 4 + 8 + \cdots + 2^{50}\\

3. \\6 + 10 + 14 + \cdots + (4n - 2)\text{.}\\

Solution

\\\d\sum\_{k=1}^{100} k\\ \\\d\sum\_{k=0}^{50} 2^k\\ \\\d\sum\_{k=2}^{n} (4k -2)\\

If we want to multiply the \\a_k\\ instead, we would write \\\d\prod\_{k=1}^n a_k\text{.}\\ For example, \\\d\prod\_{k=1}^n k = n!\text{.}\\

---

2_3_3A_Polynomial_Fitting

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/2%3A_Sequences/2.3%3A_Polynomial_Fitting

\\ \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}{&}\\

Investigate!

A standard \\8 \times 8\\ chessboard contains 64 squares. Actually, this is just the number of unit squares. How many squares of all sizes are there on a chessboard? Start with smaller boards: \\1\times 1\text{,}\\ \\2 \times 2\text{,}\\ \\3\times 3\text{,}\\ etc. Find a formula for the total number of squares in an \\n\times n\\ board.

So far we have seen methods for finding the closed formulas for arithmetic and geometric sequences. Since we know how to compute the sum of the first \\n\\ terms of arithmetic and geometric sequences, we can compute the closed formulas for sequences which have an arithmetic (or geometric) sequence of differences between terms. But what if we consider a sequence which is the sum of the first \\n\\ terms of a sequence which is itself the sum of an arithmetic sequence?

Before we get too carried away, let's consider an example: How many squares (of all sizes) are there on a chessboard? A chessboard consists of \\64\\ squares, but we also want to consider squares of longer side length. Even though we are only considering an \\8 \times 8\\ board, there is already a lot to count. So instead, let us build a sequence: the first term will be the number of squares on a \\1 \times 1\\ board, the second term will be the number of squares on a \\2 \times 2\\ board, and so on. After a little thought, we arrive at the sequence

\begin{equation\*} 1,5,14,30, 55,\ldots \end{equation\*}

This sequence is not arithmetic (or geometric for that matter), but perhaps it's sequence of differences is. For differences we get

\begin{equation\*} 4, 9, 16, 25, \ldots \end{equation\*}

Not a huge surprise: one way to count the number of squares in a \\4 \times 4\\ chessboard is to notice that there are \\16\\ squares with side length 1, 9 with side length 2, 4 with side length 3 and 1 with side length 4. So the original sequence is just the sum of squares. Now this sequence of differences is not arithmetic since it's sequence of differences (the differences of the differences of the original sequence) is not constant. In fact, this sequence of second differences is

\begin{equation\*} 5, 7, 9, \ldots \end{equation\*}

which *is* an arithmetic sequence (with constant difference 2). Notice that our original sequence had third differences (that is, differences of differences of differences of the original) constant. We will call such a sequence \\\Delta^3\\-constant. The sequence \\1, 4, 9, 16, \ldots\\ has second differences constant, so it will be a \\\Delta^2\\-constant sequence. In general, we will say a sequence is a \\\Delta^k\\-constant sequence if the \\k\\th differences are constant.

Example \\\PageIndex{1}\\

Which of the following sequences are \\\Delta^k\\-constant for some value of \\k\text{?}\\

1. \\2, 3, 7, 14, 24, 37,\ldots\text{.}\\

2. \\1, 8, 27, 64, 125, 216, \ldots\text{.}\\

3. \\1,2,4,8,16,64,128,\ldots\text{.}\\

Solution

1. This is the sequence from Example 2.2.6, in which we found a closed formula by recognizing the sequence as the sequence of partial sums of an arithmetic sequence. Indeed, the sequence of first differences is \\1,4,7, 10, 13,\ldots\text{,}\\ which itself has differences \\3,3,3,3,\ldots\text{.}\\ Thus \\2, 3, 7, 14, 24, 37,\ldots\\ is a \\\Delta^2\\-constant sequence.

2. These are the perfect cubes. The sequence of first differences is \\7, 19, 37, 61, 91, \ldots\text{;}\\ the sequence of second differences is \\12, 18, 24, 30,\ldots\text{;}\\ the sequence of third differences is constant: \\6,6,6,\ldots\text{.}\\ Thus the perfect cubes are a \\\Delta^3\\-constant sequence.

3. If we take first differences we get \\1,2,4,8,16,\ldots\text{.}\\ Wait, what? That's the sequence we started with. So taking second differences will give us the same sequence again. No matter how many times we repeat this we will always have the same sequence, which in particular means no finite number of differences will be constant. Thus this sequence is not \\\Delta^k\\-constant for any \\k\text{.}\\

The \\\Delta^0\\-constant sequences are themselves constant, so a closed formula for them is easy to compute (it's just the constant). The \\\Delta^1\\-constant sequences are arithmetic and we have a method for finding closed formulas for them as well. Every \\\Delta^2\\-constant sequence is the sum of an arithmetic sequence so we can find formulas for these as well. But notice that the format of the closed formula for a \\\Delta^2\\-constant sequence is always quadratic. For example, the square numbers are \\\Delta^2\\-constant with closed formula \\a_n= n^2\text{.}\\ The triangular numbers (also \\\Delta^2\\-constant) have closed formula \\a_n = \frac{n(n+1)}{2}\text{,}\\ which when multiplied out gives you an \\n^2\\ term as well. It appears that every time we increase the complexity of the sequence, that is, increase the number of differences before we get constants, we also increase the degree of the polynomial used for the closed formula. We go from constant to linear to quadratic. The sequence of differences between terms tells us something about the rate of growth of the sequence. If a sequence is growing at a constant rate, then the formula for the sequence will be linear. If the sequence is growing at a rate which itself is growing at a constant rate, then the formula is quadratic. You have seen this elsewhere: if a function has a constant second derivative (rate of change) then the function must be quadratic.

This works in general:

Finite Differences

The closed formula for a sequence will be a degree \\k\\ polynomial if and only if the sequence is \\\Delta^k\\-constant (i.e., the \\k\\th sequence of differences is constant).

This tells us that the sequence of numbers of squares on a chessboard, \\1, 5, 14, 30, 55, \ldots\text{,}\\ which we saw to be \\\Delta^3\\-constant, will have a cubic (degree 3 polynomial) for its closed formula.

Now once we know what format the closed formula for a sequence will take, it is much easier to actually find the closed formula. In the case that the closed formula is a degree \\k\\ polynomial, we just need \\k+1\\ data points to “fit” the polynomial to the data.

Example \\\PageIndex{2}\\

Find a formula for the sequence \\3, 7, 14, 24,\ldots\text{.}\\ Assume \\a_1 = 3\text{.}\\

Solution

First, check to see if the formula has constant differences at some level. The sequence of first differences is \\4, 7, 10, \ldots\\ which is arithmetic, so the sequence of second differences is constant. The sequence is \\\Delta^2\\-constant, so the formula for \\a_n\\ will be a degree 2 polynomial. That is, we know that for some constants \\a\text{,}\\ \\b\text{,}\\ and \\c\text{,}\\

\begin{equation\*} a_n = an^2 + bn + c. \end{equation\*}

Now to find \\a\text{,}\\ \\b\text{,}\\ and \\c\text{.}\\ First, it would be nice to know what \\a_0\\ is, since plugging in \\n = 0\\ simplifies the above formula greatly. In this case, \\a_0 = 2\\ (work backwards from the sequence of constant differences). Thus

\begin{equation\*} a_0 = 2 = a\cdot 0^2 + b \cdot 0 + c, \end{equation\*}

so \\c = 2\text{.}\\ Now plug in \\n =1\\ and \\n = 2\text{.}\\ We get

\begin{equation\*} a_1 = 3 = a + b + 2 \end{equation\*} \begin{equation\*} a_2 = 7 = a4 + b 2 + 2. \end{equation\*}

At this point we have two (linear) equations and two unknowns, so we can solve the system for \\a\\ and \\b\\ (using substitution or elimination or even matrices). We find \\a = \frac{3}{2}\\ and \\b = \frac{-1}{2}\text{,}\\ so \\a_n = \frac{3}{2} n^2 - \frac{1}{2}n + 2\text{.}\\

Example \\\PageIndex{3}\\

Find a closed formula for the number of squares on an \\n \times n\\ chessboard.

Solution

We have seen that the sequence \\1, 5, 14, 30, 55, \ldots\\ is \\\Delta^3\\-constant, so we are looking for a degree 3 polynomial. That is,

\begin{equation\*} a_n = an^3 + bn^2 + cn + d. \end{equation\*}

We can find \\d\\ if we know what \\a_0\\ is. Working backwards from the third differences, we find \\a_0 = 0\\ (unsurprisingly, since there are no squares on a \\0\times 0\\ chessboard). Thus \\d = 0\text{.}\\ Now plug in \\n = 1\text{,}\\ \\n =2\text{,}\\ and \\n =3\text{:}\\

\begin{align\*} 1 = & a + b + c\\ 5 = & 8a + 4b + 2c\\ 14 = & 27a + 9b + 3c. \end{align\*}

If we solve this system of equations we get \\a = \frac{1}{3}\text{,}\\ \\b = \frac{1}{2}\\ and \\c = \frac{1}{6}\text{.}\\ Therefore the number of squares on an \\n \times n\\ chessboard is \\a_n = \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n\text{.}\\

Note: Since the squares-on-a-chessboard problem is really asking for the sum of squares, we now have a nice formula for \\\d\sum\_{k=1}^n k^2\text{.}\\

Not all sequences will have polynomials as their closed formula. We can use the theory of finite differences to identify these.

Example \\\PageIndex{4}\\

Determine whether the following sequences can be described by a polynomial, and if so, of what degree.

1. \\1, 2, 4, 8, 16, \ldots\\

2. \\0, 7, 50, 183, 484, 1055, \ldots\\

3. \\1,1,2,3,5,8,13,\ldots\\

Solution

1. As we saw in Example 2.3.1, this sequence is not \\\Delta^k\\-constant for any \\k\text{.}\\ Therefore the closed formula for the sequence is not a polynomial. In fact, we know the closed formula is \\a_n = 2^n\text{,}\\ which grows faster than any polynomial (so is not a polynomial).

2. The sequence of first differences is \\7, 43, 133, 301, 571,\ldots\text{.}\\ The second differences are: \\36, 90, 168, 270,\ldots\text{.}\\ Third difference: \\54, 78, 102,\ldots\text{.}\\ Fourth differences: \\24, 24, \ldots\text{.}\\ As far as we can tell, this sequence of differences is constant so the sequence is \\\Delta^4\\-constant and as such the closed formula is a degree 4 polynomial.

3. This is the Fibonacci sequence. The sequence of first differences is \\0, 1, 1, 2, 3, 5, 8, \ldots\text{,}\\ the second differences are \\1, 0, 1, 1, 2, 3, 5\ldots\text{.}\\ We notice that after the first few terms, we get the original sequence back. So there will never be constant differences, so the closed formula for the Fibonacci sequence is not a polynomial.

---

2_4_3A_Solving_Recurrence_Relations

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/2%3A_Sequences/2.4%3A_Solving_Recurrence_Relations

\\ \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}{&}\\

Investigate!

Consider the recurrence relation

\begin{equation\*} a_n = 5a\_{n-1} - 6a\_{n-2}. \end{equation\*}

1. What sequence do you get if the initial conditions are \\a_0 = 1\text{,}\\ \\a_1 = 2\text{?}\\ Give a closed formula for this sequence.

2. What sequence do you get if the initial conditions are \\a_0 = 1\text{,}\\ \\a_1 = 3\text{?}\\ Give a closed formula.

3. What if \\a_0 = 2\\ and \\a_1 = 5\text{?}\\ Find a closed formula.

We have seen that it is often easier to find recursive definitions than closed formulas. Lucky for us, there are a few techniques for converting recursive definitions to closed formulas. Doing so is called solving a recurrence relation . Recall that the recurrence relation is a recursive definition without the initial conditions. For example, the recurrence relation for the Fibonacci sequence is \\F_n = F\_{n-1} + F\_{n-2}\text{.}\\ (This, together with the initial conditions \\F_0 = 0\\ and \\F_1 = 1\\ give the entire recursive *definition* for the sequence.)

Example \\\PageIndex{1}\\

Find a recurrence relation and initial conditions for \\1, 5, 17, 53, 161, 485\ldots\text{.}\\

Solution

Finding the recurrence relation would be easier if we had some context for the problem (like the Tower of Hanoi, for example). Alas, we have only the sequence. Remember, the recurrence relation tells you how to get from previous terms to future terms. What is going on here? We could look at the differences between terms: \\4, 12, 36, 108, \ldots\text{.}\\ Notice that these are growing by a factor of 3. Is the original sequence as well? \\1\cdot 3 = 3\text{,}\\ \\5 \cdot 3 = 15\text{,}\\ \\17 \cdot 3 = 51\\ and so on. It appears that we always end up with 2 less than the next term. Aha!

So \\a_n = 3a\_{n-1} + 2\\ is our recurrence relation and the initial condition is \\a_0 = 1\text{.}\\

We are going to try to *solve* these recurrence relations. By this we mean something very similar to solving differential equations: we want to find a function of \\n\\ (a closed formula) which satisfies the recurrence relation, as well as the initial condition.²Recurrence relations are sometimes called difference equations since they can describe the difference between terms and this highlights the relation to differential equations further. Just like for differential equations, finding a solution might be tricky, but checking that the solution is correct is easy.

Example \\\PageIndex{2}\\

Check that \\a_n = 2^n + 1\\ is a solution to the recurrence relation \\a_n = 2a\_{n-1} - 1\\ with \\a_1 = 3\text{.}\\

Solution

First, it is easy to check the initial condition: \\a_1\\ should be \\2^1 + 1\\ according to our closed formula. Indeed, \\2^1 + 1 = 3\text{,}\\ which is what we want. To check that our proposed solution satisfies the recurrence relation, try plugging it in.

\begin{align\*} 2a\_{n-1} - 1 \amp = 2(2^{n-1} + 1) - 1 \\ \amp = 2^n + 2 - 1 \\ \amp = 2^n +1\\ \amp = a_n. \end{align\*}

That's what our recurrence relation says! We have a solution.

Sometimes we can be clever and solve a recurrence relation by inspection. We generate the sequence using the recurrence relation and keep track of what we are doing so that we can see how to jump to finding just the \\a_n\\ term. Here are two examples of how you might do that.

Telescoping refers to the phenomenon when many terms in a large sum cancel out - so the sum “telescopes.” For example:

\begin{equation\*} (2 - 1) + (3 - 2) + (4 - 3) + \cdots + (100 - 99) + (101 - 100) = -1 + 101 \end{equation\*}

because every third term looks like: \\2 + -2 = 0\text{,}\\ and then \\3 + -3 = 0\\ and so on.

We can use this behavior to solve recurrence relations. Here is an example.

Example \\\PageIndex{3}\\

Solve the recurrence relation \\a_n = a\_{n-1} + n\\ with initial term \\a_0 = 4\text{.}\\

Solution

To get a feel for the recurrence relation, write out the first few terms of the sequence: \\4, 5, 7, 10, 14, 19, \ldots\text{.}\\ Look at the difference between terms. \\a_1 - a_0 = 1\\ and \\a_2 - a_1 = 2\\ and so on. The key thing here is that the difference between terms is \\n\text{.}\\ We can write this explicitly: \\a_n - a\_{n-1} = n\text{.}\\ Of course, we could have arrived at this conclusion directly from the recurrence relation by subtracting \\a\_{n-1}\\ from both sides.

Now use this equation over and over again, changing \\n\\ each time:

\begin{align\*} a_1 - a_0 \amp = 1\\ a_2 - a_1 \amp = 2\\ a_3 - a_2 \amp = 3\\ \vdots \quad \amp \quad \vdots\\ a_n - a\_{n-1} \amp = n. \end{align\*}

Add all these equations together. On the right-hand side, we get the sum \\1 + 2 + 3 + \cdots + n\text{.}\\ We already know this can be simplified to \\\frac{n(n+1)}{2}\text{.}\\ What happens on the left-hand side? We get

\begin{equation\*} (a_1 - a_0) + (a_2 - a_1) + (a_3 - a_2) + \cdots (a\_{n-1} - a\_{n-2})+ (a_n - a\_{n-1}). \end{equation\*}

This sum telescopes. We are left with only the \\-a_0\\ from the first equation and the \\a_n\\ from the last equation. Putting this all together we have \\-a_0 + a_n = \frac{n(n+1)}{2}\\ or \\a_n = \frac{n(n+1)}{2} + a_0\text{.}\\ But we know that \\a_0 = 4\text{.}\\ So the solution to the recurrence relation, subject to the initial condition is

\begin{equation\*} a_n = \frac{n(n+1)}{2} + 4. \end{equation\*}

(Now that we know that, we should notice that the sequence is the result of adding 4 to each of the triangular numbers.)

The above example shows a way to solve recurrence relations of the form \\a_n = a\_{n-1} + f(n)\\ where \\\sum\_{k = 1}^n f(k)\\ has a known closed formula. If you rewrite the recurrence relation as \\a_n - a\_{n-1} = f(n)\text{,}\\ and then add up all the different equations with \\n\\ ranging between 1 and \\n\text{,}\\ the left-hand side will always give you \\a_n - a_0\text{.}\\ The right-hand side will be \\\sum\_{k = 1}^n f(k)\text{,}\\ which is why we need to know the closed formula for that sum.

However, telescoping will not help us with a recursion such as \\a_n = 3a\_{n-1} + 2\\ since the left-hand side will not telescope. You will have \\-3a\_{n-1}\\'s but only one \\a\_{n-1}\text{.}\\ However, we can still be clever if we use iteration .

We have already seen an example of iteration when we found the closed formula for arithmetic and geometric sequences. The idea is, we *iterate* the process of finding the next term, starting with the known initial condition, up until we have \\a_n\text{.}\\ Then we simplify. In the arithmetic sequence example, we simplified by multiplying \\d\\ by the number of times we add it to \\a\\ when we get to \\a_n\text{,}\\ to get from \\a_n = a + d + d + d + \cdots + d\\ to \\a_n = a + dn\text{.}\\

To see how this works, let's go through the same example we used for telescoping, but this time use iteration.

Example \\\PageIndex{4}\\

Use iteration to solve the recurrence relation \\a_n = a\_{n-1} + n\\ with \\a_0 = 4\text{.}\\

Answer

Again, start by writing down the recurrence relation when \\n = 1\text{.}\\ This time, don't subtract the \\a\_{n-1}\\ terms to the other side:

\begin{equation\*} a_1 = a_0 + 1. \end{equation\*}

Now \\a_2 = a_1 + 2\text{,}\\ but we know what \\a_1\\ is. By substitution, we get

\begin{equation\*} a_2 = (a_0 + 1) + 2. \end{equation\*}

Now go to \\a_3 = a_2 + 3\text{,}\\ using our known value of \\a_2\text{:}\\

\begin{equation\*} a_3 = ((a_0 + 1) + 2) + 3. \end{equation\*}

We notice a pattern. Each time, we take the previous term and add the current index. So

\begin{equation\*} a_n = ((((a_0 + 1) +2)+3)+\cdots + n-1) + n. \end{equation\*}

Regrouping terms, we notice that \\a_n\\ is just \\a_0\\ plus the sum of the integers from \\1\\ to \\n\text{.}\\ So, since \\a_0 = 4\text{,}\\

\begin{equation\*} a_n = 4 + \frac{n(n+1)}{2}. \end{equation\*}

Of course in this case we still needed to know formula for the sum of \\1,\ldots,n\text{.}\\ Let's try iteration with a sequence for which telescoping doesn't work.

Example \\\PageIndex{5}\\

Solve the recurrence relation \\a_n = 3a\_{n-1} + 2\\ subject to \\a_0 = 1\text{.}\\

Answer

Again, we iterate the recurrence relation, building up to the index \\n\text{.}\\

\begin{align\*} a_1 \amp = 3a_0 + 2\\ a_2 \amp = 3(a_1) + 2 = 3(3a_0 + 2) + 2\\ a_3 \amp = 3$$a_2$$ + 2 = 3$$3(3a_0 + 2) + 2$$ + 2\\ \vdots \amp \qquad \vdots \qquad \qquad \vdots\\ a_n \amp = 3(a\_{n-1}) + 2 = 3(3(3(3\cdots(3a_0 + 2) + 2) + 2)\cdots + 2)+ 2. \end{align\*}

It is difficult to see what is happening here because we have to distribute all those 3's. Let's try again, this time simplifying a bit as we go.

\begin{align\*} a_1 \amp = 3a_0 + 2\\ a_2 \amp = 3(a_1) + 2 = 3(3a_0 + 2) + 2 = 3^2a_0 + 2\cdot 3 + 2\\ a_3 \amp = 3$$a_2$$ + 2 = 3$$3^2a_0 + 2\cdot 3 + 2$$ + 2 = 3^3 a_0 + 2 \cdot 3^2 + 2 \cdot 3 + 2\\ \vdots \amp \qquad\quad \vdots \hspace{2in} \vdots\\ a_n \amp = 3(a\_{n-1}) + 2 = 3(3^{n-1}a_0 + 2 \cdot 3^{n-2} + \cdots +2)+ 2\\ \amp \qquad \qquad = 3^n a_0 + 2\cdot 3^{n-1} + 2 \cdot 3^{n-2} + \cdots + 2\cdot 3 + 2. \end{align\*}

Now we simplify. \\a_0 = 1\text{,}\\ so we have \\3^n + \langle\text{stuff}\rangle\text{.}\\ Note that all the other terms have a 2 in them. In fact, we have a geometric sum with first term \\2\\ and common ratio \\3\text{.}\\ We have seen how to simplify \\2 + 2\cdot 3 + 2 \cdot 3^2 + \cdots + 2\cdot 3^{n-1}\text{.}\\ We get \\\frac{2-2\cdot 3^n}{-2}\\ which simplifies to \\3^n - 1\text{.}\\ Putting this together with the first \\3^n\\ term gives our closed formula:

\begin{equation\*} a_n = 2\cdot 3^n - 1. \end{equation\*}

Iteration can be messy, but when the recurrence relation only refers to one previous term (and maybe some function of \\n\$ it can work well. However, trying to iterate a recurrence relation such as \\a_n = 2 a\_{n-1} + 3 a\_{n-2}\\ will be way too complicated. We would need to keep track of two sets of previous terms, each of which were expressed by two previous terms, and so on. The length of the formula would grow exponentially (double each time, in fact). Luckily there happens to be a method for solving recurrence relations which works very well on relations like this.

The Characteristic Root Technique

Suppose we want to solve a recurrence relation expressed as a combination of the two previous terms, such as \\a_n = a\_{n-1} + 6a\_{n-2}\text{.}\\ In other words, we want to find a function of \\n\\ which satisfies \\a_n - a\_{n-1} - 6a\_{n-2} = 0\text{.}\\ Now iteration is too complicated, but think just for a second what would happen if we *did* iterate. In each step, we would, among other things, multiply a previous iteration by 6. So our closed formula would include \\6\\ multiplied some number of times. Thus it is reasonable to guess the solution will contain parts that look geometric. Perhaps the solution will take the form \\r^n\\ for some constant \\r\text{.}\\

The nice thing is, we know how to check whether a formula is actually a solution to a recurrence relation: plug it in. What happens if we plug in \\r^n\\ into the recursion above? We get

\begin{equation\*} r^n - r^{n-1} - 6r^{n-2} = 0. \end{equation\*}

Now solve for \\r\text{:}\\

\begin{equation\*} r^{n-2}(r^2 - r - 6) = 0, \end{equation\*}

so by factoring, \\r = -2\\ or \\r = 3\\ (or \\r = 0\text{,}\\ although this does not help us). This tells us that \\a_n = (-2)^n\\ is a solution to the recurrence relation, as is \\a_n = 3^n\text{.}\\ Which one is correct? They both are, unless we specify initial conditions. Notice we could also have \\a_n = (-2)^n + 3^n\text{.}\\ Or \\a_n = 7(-2)^n + 4\cdot 3^n\text{.}\\ In fact, for any \\a\\ and \\b\text{,}\\ \\a_n = a(-2)^n + b 3^n\\ is a solution (try plugging this into the recurrence relation). To find the values of \\a\\ and \\b\text{,}\\ use the initial conditions.

This points us in the direction of a more general technique for solving recurrence relations. Notice we will always be able to factor out the \\r^{n-2}\\ as we did above. So we really only care about the other part. We call this other part the characteristic equation for the recurrence relation. We are interested in finding the roots of the characteristic equation, which are called (surprise) the characteristic roots .

Characteristic Roots

Given a recurrence relation \\a_n + \alpha a\_{n-1} + \beta a\_{n-2} = 0\text{,}\\ the characteristic polynomial is

\begin{equation\*} x^2 + \alpha x + \beta \end{equation\*}

giving the characteristic equation :

\begin{equation\*} x^2 + \alpha x + \beta = 0. \end{equation\*}

If \\r_1\\ and \\r_2\\ are two distinct roots of the characteristic polynomial (i.e, solutions to the characteristic equation), then the solution to the recurrence relation is

\begin{equation\*} a_n = ar_1^n + br_2^n, \end{equation\*}

where \\a\\ and \\b\\ are constants determined by the initial conditions.

Example \\\PageIndex{6}\\

Solve the recurrence relation \\a_n = 7a\_{n-1} - 10 a\_{n-2}\\ with \\a_0 = 2\\ and \\a_1 = 3\text{.}\\

Solution

Rewrite the recurrence relation \\a_n - 7a\_{n-1} + 10a\_{n-2} = 0\text{.}\\ Now form the characteristic equation:

\begin{equation\*} x^2 - 7x + 10 = 0 \end{equation\*}

and solve for \\x\text{:}\\

\begin{equation\*} (x - 2) (x - 5) = 0 \end{equation\*}

so \\x = 2\\ and \\x = 5\\ are the characteristic roots. We therefore know that the solution to the recurrence relation will have the form

\begin{equation\*} a_n = a 2^n + b 5^n. \end{equation\*}

To find \\a\\ and \\b\text{,}\\ plug in \\n =0\\ and \\n = 1\\ to get a system of two equations with two unknowns:

\begin{align\*} 2 \amp = a 2^0 + b 5^0 = a + b\\ 3 \amp = a 2^1 + b 5^1 = 2a + 5b \end{align\*}

Solving this system gives \\a = \frac{7}{3}\\ and \\b = -\frac{1}{3}\\ so the solution to the recurrence relation is

\begin{equation\*} a_n = \frac{7}{3}2^n - \frac{1}{3} 5^n. \end{equation\*}

Perhaps the most famous recurrence relation is \\F_n = F\_{n-1} + F\_{n-2}\text{,}\\ which together with the initial conditions \\F_0 = 0\\ and \\F_1= 1\\ defines the Fibonacci sequence. But notice that this is precisely the type of recurrence relation on which we can use the characteristic root technique. When you do, the only thing that changes is that the characteristic equation does not factor, so you need to use the quadratic formula to find the characteristic roots. In fact, doing so gives the third most famous irrational number, \\\varphi\text{,}\\ the golden ratio .

Before leaving the characteristic root technique, we should think about what might happen when you solve the characteristic equation. We have an example above in which the characteristic polynomial has two distinct roots. These roots can be integers, or perhaps irrational numbers (requiring the quadratic formula to find them). In these cases, we know what the solution to the recurrence relation looks like.

However, it is possible for the characteristic polynomial to only have one root. This can happen if the characteristic polynomial factors as \$x - r)^2\text{.}\\ It is still the case that \\r^n\\ would be a solution to the recurrence relation, but we won't be able to find solutions for all initial conditions using the general form \\a_n = ar_1^n + br_2^n\text{,}\\ since we can't distinguish between \\r_1^n\\ and \\r_2^n\text{.}\\ We are in luck though:

Characteristic Root Technique for Repeated Roots

Suppose the recurrence relation \\a_n = \alpha a\_{n-1} + \beta a\_{n-2}\\ has a characteristic polynomial with only one root \\r\text{.}\\ Then the solution to the recurrence relation is

\begin{equation\*} a_n = ar^n + bnr^n \end{equation\*}

where \\a\\ and \\b\\ are constants determined by the initial conditions.

Notice the extra \\n\\ in \\bnr^n\text{.}\\ This allows us to solve for the constants \\a\\ and \\b\\ from the initial conditions.

Example \\\PageIndex{7}\\

Solve the recurrence relation \\a_n = 6a\_{n-1} - 9a\_{n-2}\\ with initial conditions \\a_0 = 1\\ and \\a_1 = 4\text{.}\\

Answer

The characteristic polynomial is \\x^2 - 6x + 9\text{.}\\ We solve the characteristic equation

\begin{equation\*} x^2 - 6x + 9 = 0 \end{equation\*}

by factoring:

\begin{equation\*} (x - 3)^2 = 0 \end{equation\*}

so \\x =3\\ is the only characteristic root. Therefore we know that the solution to the recurrence relation has the form

\begin{equation\*} a_n = a 3^n + bn3^n \end{equation\*}

for some constants \\a\\ and \\b\text{.}\\ Now use the initial conditions:

\begin{align\*} a_0 = 1 \amp = a 3^0 + b\cdot 0 \cdot 3^0 = a\\ a_1 = 4 \amp = a\cdot 3 + b\cdot 1 \cdot3 = 3a + 3b. \end{align\*}

Since \\a = 1\text{,}\\ we find that \\b = \frac{1}{3}\text{.}\\ Therefore the solution to the recurrence relation is

\begin{equation\*} a_n = 3^n + \frac{1}{3}n3^n. \end{equation\*}

Although we will not consider examples more complicated than these, this characteristic root technique can be applied to much more complicated recurrence relations. For example, \\a_n = 2a\_{n-1} + a\_{n-2} - 3a\_{n-3}\\ has characteristic polynomial \\x^3 - 2 x^2 - x + 3\text{.}\\ Assuming you see how to factor such a degree 3 (or more) polynomial you can easily find the characteristic roots and as such solve the recurrence relation (the solution would look like \\a_n = ar_1^n + br_2^n + cr_3^n\\ if there were 3 distinct roots). It is also possible to solve recurrence relations of the form \\a_n = \alpha a\_{n-1} + \beta a\_{n-2} + C\\ for some constant \\C\text{.}\\ It is also possible (and acceptable) for the characteristic roots to be complex numbers.

---

2_5_3A_Induction

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/2%3A_Sequences/2.5%3A_Induction

\\ \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}{&}\\

Mathematical induction is a proof technique, not unlike direct proof or proof by contradiction or combinatorial proof.³You might or might not be familiar with these yet. We will consider these in Chapter 3. In other words, induction is a style of argument we use to convince ourselves and others that a mathematical statement is always true. Many mathematical statements can be proved by simply explaining what they mean. Others are very difficult to prove—in fact, there are relatively simple mathematical statements which nobody yet knows how to prove. To facilitate the discovery of proofs, it is important to be familiar with some standard styles of arguments. Induction is one such style. Let's start with an example:

Stamps

Investigate!

You need to mail a package, but don't yet know how much postage you will need. You have a large supply of 8-cent stamps and 5-cent stamps. Which amounts of postage can you make exactly using these stamps? Which amounts are impossible to make?

Perhaps in investigating the problem above you picked some amounts of postage, and then figured out whether you could make that amount using just 8-cent and 5-cent stamps. Perhaps you did this in order: can you make 1 cent of postage? Can you make 2 cents? 3 cents? And so on. If this is what you did, you were actually answering a *sequence* of questions. We have methods for dealing with sequences. Let's see if that helps.

Actually, we will not make a sequence of questions, but rather a sequence of statements. Let \\P(n)\\ be the statement “you can make \\n\\ cents of postage using just 8-cent and 5-cent stamps.” Since for each value of \\n\text{,}\\ \\P(n)\\ is a statement, it is either true or false. So if we form the sequence of statements

\begin{equation\*} P(1), P(2), P(3), P(4), \ldots \end{equation\*}

the sequence will consist of \\T\\'s (for true) and \\F\\'s (for false). In our particular case the sequence starts

\begin{equation\*} F,F,F,F,T,F,F,T,F,F,T,F,F,T,\ldots \end{equation\*}

because \\P(1), P(2), P(3), P(4)\\ are all false (you cannot make 1, 2, 3, or 4 cents of postage) but \\P(5)\\ is true (use one 5-cent stamp), and so on.

Let's think a bit about how we could find the value of \\P(n)\\ for some specific \\n\\ (the “value” will be either \\T\\ or \\F\$. How did we find the value of the \\n\\th term of a sequence of numbers? How did we find \\a_n\text{?}\\ There were two ways we could do this: either there was a closed formula for \\a_n\text{,}\\ so we could plug in \\n\\ into the formula and get our output value, or we had a recursive definition for the sequence, so we could use the previous terms of the sequence to compute the \\n\\th term. When dealing with sequences of statements, we could use either of these techniques as well. Maybe there is a way to use \\n\\ itself to determine whether we can make \\n\\ cents of postage. That would be something like a closed formula. Or instead we could use the previous terms in the sequence (of statements) to determine whether we can make \\n\\ cents of postage. That is, if we know the value of \\P(n-1)\text{,}\\ can we get from that to the value of \\P(n)\text{?}\\ That would be something like a recursive definition for the sequence. Remember, finding recursive definitions for sequences was often easier than finding closed formulas. The same is true here.

Suppose I told you that \\P(43)\\ was true (it is). Can you determine from this fact the value of \\P(44)\\ (whether it true or false)? Yes you can. Even if we don't know how exactly we made 43 cents out of the 5-cent and 8-cent stamps, we do know that there was some way to do it. What if that way used at least three 5-cent stamps (making 15 cents)? We could replace those three 5-cent stamps with two 8-cent stamps (making 16 cents). The total postage has gone up by 1, so we have a way to make 44 cents, so \\P(44)\\ is true. Of course, we assumed that we had at least three 5-cent stamps. What if we didn't? Then we must have at least three 8-cent stamps (making 24 cents). If we replace those three 8-cent stamps with five 5-cent stamps (making 25 cents) then again we have bumped up our total by 1 cent so we can make 44 cents, so \\P(44)\\ is true.

Notice that we have not said how to make 44 cents, just that we can, on the basis that we can make 43 cents. How do we know we can make 43 cents? Perhaps because we know we can make \\42\\ cents, which we know we can do because we know we can make 41 cents, and so on. It's a recursion! As with a recursive definition of a numerical sequence, we must specify our initial value. In this case, the initial value is “\\P(1)\\ is false.” That's not good, since our recurrence relation just says that \\P(k+1)\\ is true *if* \\P(k)\\ is also true. We need to start the process with a true \\P(k)\\. So instead, we might want to use “\\P(31)\\ is true” as the initial condition.

Putting this all together we arrive at the following fact: it is possible to (exactly) make any amount of postage greater than 27 cents using just 5-cent and 8-cent stamps.⁴This is not claiming that there are no amounts less than 27 cents which can also be made. In other words, \\P(k)\\ is true for any \\k \ge 28\\. To prove this, we could do the following:

1. Demonstrate that \\P(28)\\ is true.

2. Prove that if \\P(k)\\ is true, then \\P(k+1)\\ is true (for any \\k \ge 28\$.

Suppose we have done this. Then we know that the 28th term of the sequence above is a \\T\\ (using step 1, the initial condition or base case ), and that every term after the 28th is \\T\\ also (using step 2, the recursive part or inductive case ). Here is what the proof would actually look like.

Proof

Let \\P(n)\\ be the statement “it is possible to make exactly \\n\\ cents of postage using 5-cent and 8-cent stamps.” We will show \\P(n)\\ is true for all \\n \ge 28\\.

First, we show that \\P(28)\\ is true: \\28 = 4 \cdot 5+ 1\cdot 8\text{,}\\ so we can make \\28\\ cents using four 5-cent stamps and one 8-cent stamp.

Now suppose \\P(k)\\ is true for some arbitrary \\k \ge 28\\. Then it is possible to make \\k\\ cents using 5-cent and 8-cent stamps. Note that since \\k \ge 28\text{,}\\ it cannot be that we use less than three 5-cent stamps *and* less than three 8-cent stamps: using two of each would give only 26 cents. Now if we have made \\k\\ cents using at least three 5-cent stamps, replace three 5-cent stamps by two 8-cent stamps. This replaces 15 cents of postage with 16 cents, moving from a total of \\k\\ cents to \\k+1\\ cents. Thus \\P(k+1)\\ is true. On the other hand, if we have made \\k\\ cents using at least three 8-cent stamps, then we can replace three 8-cent stamps with five 5-cent stamps, moving from 24 cents to 25 cents, giving a total of \\k+1\\ cents of postage. So in this case as well \\P(k+1)\\ is true.

Therefore, by the principle of mathematical induction, \\P(n)\\ is true for all \\n \ge 28\\.

Formalizing Proofs

What we did in the stamp example above works for many types of problems. Proof by induction is useful when trying to prove statements about all natural numbers, or all natural numbers greater than some fixed first case (like 28 in the example above), and in some other situations too. In particular, induction should be used when there is some way to go from one case to the next – when you can see how to always “do one more.”

This is a big idea. Thinking about a problem *inductively* can give new insight into the problem. For example, to really understand the stamp problem, you should think about how any amount of postage (greater than 28 cents) can be made (this is non-inductive reasoning) and also how the ways in which postage can be made *changes* as the amount increases (inductive reasoning). When you are asked to provide a proof by induction, you are being asked to think about the problem *dynamically*; how does increasing \\n\\ change the problem?

But there is another side to proofs by induction as well. In mathematics, it is not enough to understand a problem, you must also be able to communicate the problem to others. Like any discipline, mathematics has standard language and style, allowing mathematicians to share their ideas efficiently. Proofs by induction have a certain formal style, and being able to write in this style is important. It allows us to keep our ideas organized and might even help us with formulating a proof.

Here is the general structure of a proof by mathematical induction:

Induction Proof Structure

Start by saying what the statement is that you want to prove: “Let \\P(n)\\ be the statement…” To prove that \\P(n)\\ is true for all \\n \ge 0\text{,}\\ you must prove two facts:

1. Base case: Prove that \\P(0)\\ is true. You do this directly. This is often easy.

2. Inductive case: Prove that \\P(k) \imp P(k+1)\\ for all \\k \ge 0\\. That is, prove that for any \\k \ge 0\\ if \\P(k)\\ is true, then \\P(k+1)\\ is true as well. This is the proof of an if … then … statement, so you can assume \\P(k)\\ is true (\\P(k)\\ is called the *inductive hypothesis*). You must then explain why \\P(k+1)\\ is also true, given that assumption.

Assuming you are successful on both parts above, you can conclude, “Therefore by the principle of mathematical induction, the statement \\P(n)\\ is true for all \\n \ge 0\\.”

Sometimes the statement \\P(n)\\ will only be true for values of \\n \ge 4\text{,}\\ for example, or some other value. In such cases, replace all the 0's above with 4's (or the other value).

The other advantage of formalizing inductive proofs is it allows us to verify that the logic behind this style of argument is valid. Why does induction work? Think of a row of dominoes set up standing on their edges. We want to argue that in a minute, all the dominoes will have fallen down. For this to happen, you will need to push the first domino. That is the base case. It will also have to be that the dominoes are close enough together that when any particular domino falls, it will cause the next domino to fall. That is the inductive case. If both of these conditions are met, you push the first domino over and each domino will cause the next to fall, then all the dominoes will fall.

Induction is powerful! Think how much easier it is to knock over dominoes when you don't have to push over each domino yourself. You just start the chain reaction, and the rely on the relative nearness of the dominoes to take care of the rest.

Think about our study of sequences. It is easier to find recursive definitions for sequences than closed formulas. Going from one case to the next is easier than going directly to a particular case. That is what is so great about induction. Instead of going directly to the (arbitrary) case for \\n\text{,}\\ we just need to say how to get from one case to the next.

When you are asked to prove a statement by mathematical induction, you should first think about *why* the statement is true, using inductive reasoning. Explain why induction is the right thing to do, and roughly why the inductive case will work. Then, sit down and write out a careful, formal proof using the structure above.

Examples

Here are some examples of proof by mathematical induction.

Example \\\PageIndex{1}\\

Prove for each natural number \\n \ge 1\\ that \\1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\\.

Answer

First, let's think inductively about this equation. In fact, we know this is true for other reasons (reverse and add comes to mind). But why might induction be applicable? The left-hand side adds up the numbers from 1 to \\n\\. If we know how to do that, adding just one more term (\\n+1\$ would not be that hard. For example, if \\n = 100\text{,}\\ suppose we know that the sum of the first 100 numbers is \\5050\\ (so \\1 + 2 + 3 + \cdots + 100 = 5050\text{,}\\ which is true). Now to find the sum of the first 101 numbers, it makes more sense to just add 101 to 5050, instead of computing the entire sum again. We would have \\1 + 2 + 3 + \cdots + 100 + 101 = 5050 + 101 = 5151\\. In fact, it would always be easy to add just one more term. This is why we should use induction.

Now the formal proof:

Proof

Let \\P(n)\\ be the statement \\1 + 2 + 3 + \cdots + n = \frac{n(n+2)}{2}\\. We will show that \\P(n)\\ is true for all natural numbers \\n \ge 1\\.

Base case: \\P(1)\\ is the statement \\1 = \frac{1(1+1)}{2}\\ which is clearly true.

Inductive case: Let \\k \ge 1\\ be a natural number. Assume (for induction) that \\P(k)\\ is true. That means \\1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}\\. We will prove that \\P(k+1)\\ is true as well. That is, we must prove that \\1 + 2 + 3 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}\\. To prove this equation, start by adding \\k+1\\ to both sides of the inductive hypothesis:

\begin{equation\*} 1 + 2 + 3 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1). \end{equation\*}

Now, simplifying the right side we get:

\begin{align\*} \frac{k(k+1)}{2} + k+1 \amp = \frac{k(k+1)}{2} + \frac{2(k+1)}{2}\\ \amp = \frac{k(k+1) + 2(k+1)}{2}\\ \amp = \frac{(k+2)(k+1)}{2}. \end{align\*}

Thus \\P(k+1)\\ is true, so by the principle of mathematical induction \\P(n)\\ is true for all natural numbers \\n \ge 1\\.

Note that in the part of the proof in which we proved \\P(k+1)\\ from \\P(k)\text{,}\\ we used the equation \\P(k)\\. This was the inductive hypothesis. Seeing how to use the inductive hypotheses is usually straight forward when proving a fact about a sum like this. In other proofs, it can be less obvious where it fits in.

Example \\\PageIndex{2}\\

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

Solution

Again, start by understanding the dynamics of the problem. What does increasing \\n\\ do? Let's try with a few examples. If \\n = 1\text{,}\\ then yes, \\6^1 - 1 = 5\\ is a multiple of 5. What does incrementing \\n\\ to 2 look like? We get \\6^2 - 1 = 35\text{,}\\ which again is a multiple of 5. Next, \\n = 3\text{:}\\ but instead of just finding \\6^3 - 1\text{,}\\ what did the increase in \\n\\ do? We will still subtract 1, but now we are multiplying by another 6 first. Viewed another way, we are multiplying a number which is one more than a multiple of 5 by 6 (because \\6^2 - 1\\ is a multiple of 5, so \\6^2\\ is one more than a multiple of 5). What do numbers which are one more than a multiple of 5 look like? They must have last digit 1 or 6. What happens when you multiply such a number by 6? Depends on the number, but in any case, the last digit of the new number must be a 6. And then if you subtract 1, you get last digit 5, so a multiple of 5.

The point is, every time we multiply by just one more six, we still get a number with last digit 6, so subtracting 1 gives us a multiple of 5. Now the formal proof:

Proof

Let \\P(n)\\ be the statement, “\\6^n - 1\\ is a multiple of 5.” We will prove that \\P(n)\\ is true for all \\n \in \N\\.

Base case: \\P(0)\\ is true: \\6^0 -1 = 0\\ which is a multiple of 5.

Inductive case: Let \\k\\ be an arbitrary natural number. Assume, for induction, that \\P(k)\\ is true. That is, \\6^k - 1\\ is a multiple of \\5\\. Then \\6^k - 1 = 5j\\ for some integer \\j\\. This means that \\6^k = 5j + 1\\. Multiply both sides by \\6\text{:}\\

\begin{equation\*} 6^{k+1} = 6(5j+1) = 30j + 6. \end{equation\*}

But we want to know about \\6^{k+1} - 1\text{,}\\ so subtract 1 from both sides:

\begin{equation\*} 6^{k+1} - 1 = 30j + 5. \end{equation\*}

Of course \\30j+5 = 5(6j+1)\text{,}\\ so is a multiple of 5.

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

We had to be a little bit clever (i.e., use some algebra) to locate the \\6^k - 1\\ inside of \\6^{k+1} - 1\\ before we could apply the inductive hypothesis. This is what can make inductive proofs challenging.

In the two examples above, we started with \\n = 1\\ or \\n = 0\\. We can start later if we need to.

Example \\\PageIndex{3}\\

Prove that \\n^2 \lt 2^n\\ for all integers \\n \ge 5\\.

Solution

First, the idea of the argument. What happens when we increase \\n\\ by 1? On the left-hand side, we increase the base of the square and go to the next square number. On the right-hand side, we increase the power of 2. This means we double the number. So the question is, how does doubling a number relate to increasing to the next square? Think about what the difference of two consecutive squares looks like. We have \$n+1)^2 - n^2\\. This factors:

\begin{equation\*} (n+1)^2 - n^2 = (n+1-n)(n+1+n) = 2n+1. \end{equation\*}

But doubling the right-hand side increases it by \\2^n\text{,}\\ since \\2^{n+1} = 2^n + 2^n\\. When \\n\\ is large enough, \\2^n \> 2n + 1\\.

What we are saying here is that each time \\n\\ increases, the left-hand side grows by less than the right-hand side. So if the left-hand side starts smaller (as it does when \\n = 5\$, it will never catch up.

Now the formal proof:

Let \\P(n)\\ be the statement \\n^2 \lt 2^n\\. We will prove \\P(n)\\ is true for all integers \\n \ge 5\\.

Base case: \\P(5)\\ is the statement \\5^2 \lt 2^5\\. Since \\5^2 = 25\\ and \\2^5 = 32\text{,}\\ we see that \\P(5)\\ is indeed true.

Inductive case: Let \\k \ge 5\\ be an arbitrary integer. Assume, for induction, that \\P(k)\\ is true. That is, assume \\k^2 \lt 2^k\\. We will prove that \\P(k+1)\\ is true, i.e., \$k+1)^2 \lt 2^{k+1}\\. To prove such an inequality, start with the left-hand side and work towards the right-hand side:

\begin{align\*} (k+1)^2 \amp = k^2 + 2k + 1 \amp\\ \amp \lt 2^k + 2k + 1 \amp \ldots\text{by the inductive hypothesis.}\\ \amp \lt 2^k + 2^k \amp \ldots\text{ since } 2k + 1 \lt 2^k \text{ for }k \ge 5.\\ \amp = 2^{k+1}. \amp \end{align\*}

Following the equalities and inequalities through, we get \$k+1)^2 \lt 2^{k+1}\text{,}\\ in other words, \\P(k+1)\\. Therefore by the principle of mathematical induction, \\P(n)\\ is true for all \\n \ge 5\\.

\\\square\\

The previous example might remind you of the *racetrack principle* from calculus, which says that if \\f(a) \lt g(a)\text{,}\\ and \\f'(x) \lt g'(x)\\ for \\x \> a\text{,}\\ then \\f(x) \lt g(x)\\ for \\x \> a\\. Same idea: the larger function is increasing at a faster rate than the smaller function, so the larger function will stay larger. In discrete math, we don't have derivatives, so we look at differences. Thus induction is the way to go.

Warning:

With great power, comes great responsibility. Induction isn't magic. It seems very powerful to be able to assume \\P(k)\\ is true. After all, we are trying to prove \\P(n)\\ is true and the only difference is in the variable: \\k\\ vs. \\n\\. Are we assuming that what we want to prove is true? Not really. We assume \\P(k)\\ is true only for the sake of proving that \\P(k+1)\\ is true.

Still you might start to believe that you can prove anything with induction. Consider this incorrect “proof” that every Canadian has the same eye color: Let \\P(n)\\ be the statement that any \\n\\ Canadians have the same eye color. \\P(1)\\ is true, since everyone has the same eye color as themselves. Now assume \\P(k)\\ is true. That is, assume that in any group of \\k\\ Canadians, everyone has the same eye color. Now consider an arbitrary group of \\k+1\\ Canadians. The first \\k\\ of these must all have the same eye color, since \\P(k)\\ is true. Also, the last \\k\\ of these must have the same eye color, since \\P(k)\\ is true. So in fact, everyone the group must have the same eye color. Thus \\P(k+1)\\ is true. So by the principle of mathematical induction, \\P(n)\\ is true for all \\n\\.

Clearly something went wrong. The problem is that the proof that \\P(k)\\ implies \\P(k+1)\\ assumes that \\k \ge 2\\. We have only shown \\P(1)\\ is true. In fact, \\P(2)\\ is false.

Strong Induction

Investigate!

Start with a square piece of paper. You want to cut this square into smaller squares, leaving no waste (every piece of paper you end up with must be a square). Obviously it is possible to cut the square into 4 squares. You can also cut it into 9 squares. It turns out you can cut the square into 7 squares (although not all the same size). What other numbers of squares could you end up with?

Sometimes, to prove that \\P(k+1)\\ is true, it would be helpful to know that \\P(k)\\ *and* \\P(k-1)\\ *and* \\P(k-2)\\ are all true. Consider the following puzzle:

> You have a rectangular chocolate bar, made up of \\n\\ identical squares of chocolate. You can take such a bar and break it along any row or column. How many times will you have to break the bar to reduce it to \\n\\ single chocolate squares?

At first, this question might seem impossible. Perhaps I meant to ask for the *smallest* number of breaks needed? Let's investigate.

Start with some small cases. If \\n=2\text{,}\\ you must have a \\1\times 2\\ rectangle, which can be reduced to single pieces in one break. With \\n=3\text{,}\\ we must have a \\1\times 3\\ bar, which requires two breaks: the first break creates a single square and a \\1\times 2\\ bar, which we know takes one (more) break.

What about \\n=4\text{?}\\ Now we could have a \\2\times 2\\ bar, or a \\1 \times 4\\ bar. In the first case, break the bar into two \\2\times 2\\ bars, each which require one more break (that's a total of three breaks required). If we started with a \\1 \times 4\\ bar, we have choices for our first break. We could break the bar in half, creating two \\1\times 2\\ bars, or we could break off a single square, leaving a \\1\times 3\\ bar. But either way, we still need two more breaks, giving a total of three.

It is starting to look like no matter how we break the bar (and no matter how the \\n\\ squares are arranged into a rectangle), we will always have the same number of breaks required. It also looks like that number is one less than \\n\text{:}\\

Conjecture2.5.4

Given a \\n\\-square rectangular chocolate bar, it always takes \\n-1\\ breaks to reduce the bar to single squares.

It makes sense to prove this by induction because after breaking the bar once, you are left with *smaller* chocolate bars. Reducing to smaller cases is what induction is all about. We can inductively assume we already know how to deal with these smaller bars. The problem is, if we are trying to prove the inductive case about a \$k+1)\\-square bar, we don't know that after the first break the remaining bar will have \\k\\ squares. So we really need to assume that our conjecture is true for all cases less than \\k+1\\.

Is it valid to make this stronger assumption? Remember, in induction we are attempting to prove that \\P(n)\\ is true for all \\n\\. What if that were not the case? Then there would be some first \\n_0\\ for which \\P(n_0)\\ was false. Since \\n_0\\ is the *first* counterexample, we know that \\P(n)\\ is true for all \\n \lt n_0\\. Now we proceed to prove that \\P(n_0)\\ is actually true, based on the assumption that \\P(n)\\ is true for all smaller \\n\\.

This is quite an advantage: we now have a stronger inductive hypothesis. We can assume that \\P(1)\text{,}\\ \\P(2)\text{,}\\ \\P(3)\text{,}\\ … \\P(k)\\ is true, just to show that \\P(k+1)\\ is true. Previously, we just assumed \\P(k)\\ for this purpose.

It is slightly easier if we change our variables for strong induction. Here is what the formal proof would look like:

Strong Induction Proof Structure

Again, start by saying what you want to prove: “Let \\P(n)\\ be the statement…” Then establish two facts:

1. Base case: Prove that \\P(0)\\ is true.

2. Inductive case: Assume \\P(k)\\ is true for all \\k \lt n\\. Prove that \\P(n)\\ is true.

Conclude, “therefore, by strong induction, \\P(n)\\ is true for all \\n \gt 0\\.”

Of course, it is acceptable to replace 0 with a larger base case if needed.⁵Technically, strong induction does not require you to prove a separate base case. This is because when proving the inductive case, you must show that \\P(0)\\ is true, assuming \\P(k)\\ is true for all \\k \lt 0\\. But this is not any help so you end up proving \\P(0)\\ anyway. To be on the safe side, we will always include the base case separately.

Let's prove our conjecture about the chocolate bar puzzle:

Proof

Let \\P(n)\\ be the statement, “it takes \\n-1\\ breaks to reduce a \\n\\-square chocolate bar to single squares.”

Base case: Consider \\P(2)\\. The squares must be arranged into a \\1\times 2\\ rectangle, and we require \\2-1 = 1\\ breaks to reduce this to single squares.

Inductive case: Fix an arbitrary \\n\ge 2\\ and assume \\P(k)\\ is true for all \\k \lt n\\. Consider a \\n\\-square rectangular chocolate bar. Break the bar once along any row or column. This results in two chocolate bars, say of sizes \\a\\ and \\b\\. That is, we have an \\a\\-square rectangular chocolate bar, a \\b\\-square rectangular chocolate bar, and \\a+b = n\\.

We also know that \\a \lt n\\ and \\b \lt n\text{,}\\ so by our inductive hypothesis, \\P(a)\\ and \\P(b)\\ are true. To reduce the \\a\\-sqaure bar to single squares takes \\a-1\\ breaks; to reduce the \\b\\-square bar to single squares takes \\b-1\\ breaks. Doing this results in our original bar being reduced to single squares. All together it took the initial break, plus the \\a-1\\ and \\b-1\\ breaks, for a total of \\1+a-1+b-1 = a+b-1 = n-1\\ breaks. Thus \\P(n)\\ is true.

Therefore, by strong induction, \\P(n)\\ is true for all \\n \ge 2\\.

Here is a more mathematically relevant example:

Example \\\PageIndex{5}\\

Prove that any natural number greater than 1 is either prime or can be written as the product of primes.

Solution

First, the idea: if we take some number \\n\text{,}\\ maybe it is prime. If so, we are done. If not, then it is composite, so it is the product of two smaller numbers. Each of these factors is smaller than \\n\\ (but at least 2), so we can repeat the argument with these numbers. We have reduced to a smaller case.

Now the formal proof:

Proof

Let \\P(n)\\ be the statement, “\\n\\ is either prime or can be written as the product of primes.” We will prove \\P(n)\\ is true for all \\n \ge 2\\.

Base case: \\P(2)\\ is true because \\2\\ is indeed prime.

Inductive case: assume \\P(k)\\ is true for all \\k \lt n\\. We want to show that \\P(n)\\ is true. That is, we want to show that \\n\\ is either prime or is the product of primes. If \\n\\ is prime, we are done. If not, then \\n\\ has more than 2 divisors, so we can write \\n = m_1 \cdot m_2\text{,}\\ with \\m_1\\ and \\m_2\\ less than \\n\\ (and greater than 1). By the inductive hypothesis, \\m_1\\ and \\m_2\\ are each either prime or can be written as the product of primes. In either case, we have that \\n\\ is written as the product of primes.

Thus by the strong induction, \\P(n)\\ is true for all \\n \ge 2\\.

Whether you use regular induction or strong induction depends on the statement you want to prove. If you wanted to be safe, you could always use strong induction. It really is *stronger*, so can accomplish everything “weak” induction can. That said, using regular induction is often easier since there is only one place you can use the induction hypothesis. There is also something to be said for *elegance* in proofs. If you can prove a statement using simpler tools, it is nice to do so.

As a final contrast between the two forms of induction, consider once more the stamp problem. Regular induction worked by showing how to increase postage by one cent (either replacing three 5-cent stamps with two 8-cent stamps, or three 8-cent stamps with five 5-cent stamps). We could give a slightly different proof using strong induction. First, we could show *five* base cases: it is possible to make 28, 29, 30, 31, and 32 cents (we would actually say how each of these is made). Now assume that it is possible to make \\k\\ cents of postage for all \\k \lt n\\ as long as \\k \ge 28\\. As long as \\n \> 32\text{,}\\ this means in particular we can make \\k = n-5\\ cents. Now add a 5-cent stamp to get make \\n\\ cents.

---

2_E_3A_Sequences__Exercises_

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/2%3A_Sequences/2.E%3A_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:

\![$$(https://math.libretexts.org/images/image-47.svg)

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:

\![$$(https://math.libretexts.org/images/image-50.svg) \![$$(https://math.libretexts.org/images/image-51.svg) \![$$(https://math.libretexts.org/images/image-52.svg)

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 *n*th 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.

---

2_S_3ASequencesSummary_

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/2%3A_Sequences/2.S%3A__Sequences_(Summary)

\\ \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}{&}\\

Investigate!

Each day your supply of magic chocolate covered espresso beans doubles (each one splits in half), but then you eat 5 of them. You have 10 at the start of day 0.

1. Write out the first few terms of the sequence. Then give a recursive definition for the sequence and explain how you know it is correct.

2. Prove, using induction, that the last digit of the number of beans you have on the \\n\\th day is always a 5 for all \\n \ge 1\text{.}\\

3. Find a closed formula for the \\n\\th term of the sequence and prove it is correct by induction.

In this chapter we explored sequences and mathematical induction. At first these might not seem entirely related, but there is a link: recursive reasoning. When we have many cases (maybe infinitely many), it is often easier to describe a particular case by saying how it relates to other cases, instead of describing it absolutely. For sequences, we can describe the \\n\\th term in the sequence by saying how it is related to the *previous* term. When showing a statement involving the variable \\n\\ is true for all values of \\n\text{,}\\ we can describe why the case for \\n = k\\ is true on the basis of why the case for \\n = k-1\\ is true.

While thinking of problems recursively is often easer than thinking of them absolutely (at least after you get used to thinking in this way), our ultimate goal is to move beyond this recursive description. For sequences, we want to find *closed formulas* for the \\n\\th term of the sequence. For proofs, we want to know the statement is actually true for a particular \\n\\ (not only under the assumption that the statement is true for the previous value of \\n\$. In this chapter we saw some methods for moving from recursive descriptions to absolute descriptions.

If the terms of a sequence increase by a constant difference or constant ratio (these are both recursive descriptions), then the sequences are arithmetic or geometric, respectively, and we have closed formulas for each of these based on the initial terms and common difference or ratio.
If the terms of a sequence increase at a polynomial rate (that is, if the differences between terms form a sequence with a polynomial closed formula), then the sequence is itself given by a polynomial closed formula (of degree one more than the sequence of differences).
If the terms of a sequence increase at an exponential rate, then we expect the closed formula for the sequence to be exponential. These sequences often have relatively nice recursive formulas, and the *characteristic root technique* allows us to find the closed formula for these sequences.
If we want to prove that a statement is true for all values of \\n\\ (greater than some first small value), and we can describe why the statement being true for \\n = k\\ implies the statement is true for \\n = k+1\text{,}\\ then the *principle of mathematical induction* gives us that the statement is true for all values of \\n\\ (greater than the base case).

Throughout the chapter we tried to understand *why* these facts listed above are true. In part, that is what proofs, by induction or not, attempt to accomplish: they explain why mathematical truths are in fact truths. As we develop our ability to reason about mathematics, it is a good idea to make sure that the methods of our reasoning are sound. The branch of mathematics that deals with deciding whether reasoning is good or not is *mathematical logic*, the subject of the next chapter.

Chapter Review

1

Find \\3 + 7 + 11+ \cdots + 427\text{.}\\

Answer

\\\frac{430\cdot 107}{2} = 23005\text{.}\\

2

Consider the sequence \\2, 6, 10, 14, \ldots, 4n + 6\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.

2. \\4n+2\text{.}\\

3. \\\frac{(4n+8)(n+2)}{2}\text{.}\\

3

Consider the sequence given by \\a_n = 2\cdot 5^{n-1}\text{.}\\

1. Find the first 4 terms of the sequence. What sort of sequence is this?

2. Find the *sum* of the first 25 terms. That is, compute \\\d\sum\_{k=1}^{25}a_k\text{.}\\

Answer

1. \\2, 10, 50, 250, \ldots\\ The sequence is geometric.

2. \\\frac{2 - 2\cdot 5^{25}}{-4}\text{.}\\

4

Consider the sequence \\5, 11, 19, 29, 41, 55,\ldots\text{.}\\ Assume \\a_1 = 5\text{.}\\

1. Find a closed formula for \\a_n\text{,}\\ the \\n\\th term of the sequence, by writing each term as a sum of a sequence. Hint: first find \\a_0\text{,}\\ but ignore it when collapsing the sum.

2. Find a closed formula again, this time using either polynomial fitting or the characteristic root technique (whichever is appropriate). Show your work.

3. Find a closed formula once again, this time by recognizing the sequence as a modification to some well known sequence(s). Explain.

5

Use polynomial fitting to find a closed formula for the sequence \$a_n)\_{n\ge 1}\text{:}\\

\begin{equation\*} 4, 11, 20, 31, 44, \ldots. \end{equation\*}

Answer

\\a_n = n^2 + 4n - 1\text{.}\\

6

Suppose the closed formula for a particular sequence is a degree 3 polynomial. What can you say about the closed formula for:

1. The sequence of partial sums.

2. The sequence of second differences.

Answer

1. The sequence of partial sums will be a degree 4 polynomial (its sequence of differences will be the original sequence).

2. The sequence of second differences will be a degree 1 polynomial - an arithmetic sequence.

7

Consider the sequence given recursively by \\a_1 = 4\text{,}\\ \\a_2 = 6\\ and \\a_n = a\_{n-1} + a\_{n-2}\text{.}\\

1. Write out the first 6 terms of the sequence.

2. Could the closed formula for \\a_n\\ be a polynomial? Explain.

Answer

1. \\4, 6, 10, 16, 26, 42, \ldots\text{.}\\

2. No, taking differences gives the original sequence back, so the differences will never be constant.

8

The sequence \\-1, 0, 2, 5, 9, 14\ldots\\ has closed formula \\a_n = \dfrac{(n+1)(n-2)}{2}\text{.}\\ Use this fact to find a closed formula for the sequence \\4, 10, 18, 28, 40, \ldots\text{.}\\

Answer

\\b_n = (n+3)n\text{.}\\

9

The in song *The Twelve Days of Christmas*, my true love gave to me first 1 gift, then 2 gifts and 1 gift, then 3 gifts, 2 gifts and 1 gift, and so on. How many gifts did my true love give me all together during the twelve days?

10

Consider the recurrence relation \\a_n = 3a\_{n-1} + 10 a\_{n-2}\\ with first two terms \\a_0 = 1\\ and \\a_1 = 2\text{.}\\

1. Write out the first 5 terms of the sequence defined by this recurrence relation.

2. Solve the recurrence relation. That is, find a closed formula for \\a_n\text{.}\\

Answer

1. \\1, 2, 16,68, 364, \ldots\text{.}\\

2. \\a_n = \frac{3}{7}(-2)^n + \frac{4}{7}5^n\text{.}\\

11

Consider the recurrence relation \\a_n = 2a\_{n-1} + 8a\_{n-2}\text{,}\\ with initial terms \\a_0 = 1\\ and \\a_1= 3\text{.}\\

1. Find the next two terms of the sequence (\\a_2\\ and \\a_3\$.

2. Solve the recurrence relation. That is, find a closed formula for the \\n\\th term of the sequence.

Answer

1. \\a_2 = 14\text{.}\\ \\a_3 = 52\text{.}\\

2. \\a_n = \frac{1}{6}(-2)^n + \frac{5}{6}4^n\text{.}\\

12

Your magic chocolate bunnies reproduce like rabbits: every large bunny produces 2 new mini bunnies each day, and each day every mini bunny born the previous day grows into a large bunny. Assume you start with 2 mini bunnies and no bunny ever dies (or gets eaten).

1. Write out the first few terms of the sequence.

2. Give a recursive definition of the sequence and explain why it is correct.

3. Find a closed formula for the \\n\\th term of the sequence.

Answer

1. On the first day, your 2 mini bunnies become 2 large bunnies. On day 2, your two large bunnies produce 4 mini bunnies. On day 3, you have 4 mini bunnies (produced by your 2 large bunnies) plus 6 large bunnies (your original 2 plus the 4 newly matured bunnies). On day 4, you will have \\12\\ mini bunnies (2 for each of the 6 large bunnies) plus 10 large bunnies (your previous 6 plus the 4 newly matured). The sequence of total bunnies is \\2, 2, 6, 10, 22, 42\ldots\\ starting with \\a_0 = 2\\ and \\a_1 = 2\text{.}\\

2. \\a_n = a\_{n-1} + 2a\_{n-2}\text{.}\\ This is because the number of bunnies is equal to the number of bunnies you had the previous day (both mini and large) plus 2 times the number you had the day before that (since all bunnies you had 2 days ago are now large and producing 2 new bunnies each).

3. Using the characteristic root technique, we find \\a_n = a2^n + b(-1)^n\text{,}\\ and we can find \\a\\ and \\b\\ to give \\a_n = \frac{4}{3}2^n + \frac{2}{3}(-1)^n\text{.}\\

13

Prove the following statements by mathematical induction:

1. \\n! \lt n^n\\ for \\n \ge 2\\

2. \\\d\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} +\frac{1}{3\cdot 4}+\cdots + \frac{1}{n\cdot(n+1)} = \d\frac{n}{n+1}\\ for all \\n \in \Z^+\text{.}\\

3. \\4^n - 1\\ is a multiple of 3 for all \\n \in \N\text{.}\\

4. The *greatest* amount of postage you *cannot* make exactly using 4 and 9 cent stamps is 23 cents.

5. Every even number squared is divisible by 4.

Answer

1. Hint: \$n+1)^{n+1} \> (n+1) \cdot n^{n}\text{.}\\

2. Hint: This should be similar to the other sum proofs. The last bit comes down to adding fractions.

3. Hint: Write \\4^{k+1} - 1 = 4\cdot 4^k - 4 + 3\text{.}\\

4. Hint: one 9-cent stamp is 1 more than two 4-cent stamps, and seven 4-cent stamps is 1 more than three 9-cent stamps.

5. Careful to actually use induction here. The base case: \\2^2 = 4\text{.}\\ The inductive case: assume \$2n)^2\\ is divisible by 4 and consider \$2n+2)^2 = (2n)^2 + 4n + 4\text{.}\\ This is divisible by 4 because \\4n +4\\ clearly is, and by our inductive hypothesis, so is \$2n)^2\text{.}\\

14

Prove \\1^3 + 2^3 + 3^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2\\ holds for all \\n \ge 1\text{,}\\ by mathematical induction.

Hin

This is a straight forward induction proof. Note you will need to simplify \\\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3\\ and get \\\left(\frac{(n+1)(n+2)}{2}\right)^2\text{.}\\

15

Suppose \\a_0 = 1\text{,}\\ \\a_1 = 1\\ and \\a_n = 3a\_{n-1} - 2a\_{n-1}\text{.}\\ Prove, using strong induction, that \\a_n = 1\\ for all \\n\text{.}\\

Hint

There are two base cases \\P(0)\\ and \\P(1)\text{.}\\ Then, for the inductive case, assume \\P(k)\\ is true for all \\k \lt n\text{.}\\ This allows you to assume \\a\_{n-1} = 1\\ and \\a\_{n-2} = 1\text{.}\\ Apply the recurrence relation.

16

Prove, using strong induction, that every positive integer can be written as the sum of distinct powers of 2. For example, \\13 = 1 + 4 + 8 = 2^0 + 2^2 + 2^3\text{.}\\

Answer

Note that \\1 = 2^0\text{;}\\ this is your base case. Now suppose \\k\\ can be written as the sum of distinct powers of 2 for all \\1\le k \le n\text{.}\\ We can then write \\n\\ as the sum of distinct powers of 2 as follows: subtract the largest power of 2 less than \\n\\ from \\n\text{.}\\ That is, write \\n = 2^j + k\\ for the largest possible \\j\text{.}\\ But \\k\\ is now less than \\n\text{,}\\ and also less than \\2^j\text{,}\\ so write \\k\\ as the sum of distinct powers of 2 (we can do so by the inductive hypothesis). Thus \\n\\ can be written as the sum of distinct powers of 2 for all \\n \ge 1\text{.}\\

17

Prove using induction that every set containing \\n\\ elements has \\2^n\\ different subsets for any \\n \ge 1\text{.}\\

Answer

Let \\P(n)\\ be the statement, “every set containing \\n\\ elements has \\2^n\\ different subsets.” We will show \\P(n)\\ is true for all \\n \ge 1\text{.}\\ Base case: Any set with 1 element \\\\a\\\\ has exactly 2 subsets: the empty set and the set itself. Thus the number of subsets is \\2= 2^1\text{.}\\ Thus \\P(1)\\ is true. Inductive case: Suppose \\P(k)\\ is true for some arbitrary \\k \ge 1\text{.}\\ Thus every set containing exactly \\k\\ elements has \\2^k\\ different subsets. Now consider a set containing \\k+1\\ elements: \\A = \\a_1, a_2, \ldots, a_k, a\_{k+1}\\\text{.}\\ Any subset of \\A\\ must either contain \\a\_{k+1}\\ or not. In other words, a subset of \\A\\ is just a subset of \\\\a_1, a_2,\ldots, a_k\\\\ with or without \\a\_{k+1}\text{.}\\ Thus there are \\2^k\\ subsets of \\A\\ which contain \\a\_{k+1}\\ and another \\2^{k+1}\\ subsets of \\A\\ which do not contain \\a^{k+1}\text{.}\\ This gives a total of \\2^k + 2^k = 2\cdot 2^k = 2^{k+1}\\ subsets of \\A\text{.}\\ But our choice of \\A\\ was arbitrary, so this works for any subset containing \\k+1\\ elements, so \\P(k+1)\\ is true. Therefore, by the principle of mathematical induction, \\P(n)\\ is true for all \\n \ge 1\text{.}\\

---

← 1 1 3A Additive and Multiplicative Principles 3 0 3A Prelude to Symbolic Logic and Proofs →