Ch.5: Sequences, Mathematical Induction, and Recursion

Chapter 5 of the book "Discrete Mathematics with Applications" by Susanna S. Epp (4th edition) 5.1. Sequences 5.2. Mathematical Induction I 5.3. Mathematical Induction II 5.4. Strong Mathematical Induction and the Well-Ordering Principle for the Integers 5.5. Application: Correctness of Algorithms 5.6. Defining Sequences Recursively 5.7. Solving Recurrence Relations by Iteration 5.8. Second-Order Linear Homogeneous Recurrence Relations with Constant Coefficients 5.9. General Recursive Definitions and Structural Induction

234 flashcards · Mathematics · by lakesare

Part of Textbooks › Discrete Mathematics with Applications (Susanna Epp) · 12 courses

[Sequences] A person has 2 parents, 4 grandparents, 8 great-grandparents, and so on. Let AkA_kAk be the number of ancestors in the kkk th generation back. Which formula does the pattern suggest?
Ak=2k\boldsymbol{A_k = 2^k}Ak=2k Strictly, the true AkA_kAk is less than 2k2^k2k for large kkk , because one ancestor can appear on several branches of the family tree.Example: A3=23=8A_3 = 2^3 = 8A3=23=8 great-grandparents.
[Sequences] The symbol "…", shorthand for "and so forth", is called an ellipsis.
Example: 2,4,8,16,…2, 4, 8, 16, \ldots2,4,8,16,…
[Sequences] What is a sequence?
A function whose domain is either all the integers between two given integers or all the integers ≥\ge≥ a given integer. Example: ak=2ka_k = 2^kak=2k for all integers k≥1k \ge 1k≥1 gives the sequence 2,4,8,16,…2, 4, 8, 16, \ldots2,4,8,16,…
[Sequences] In the sequence am,am+1,am+2,…,ana_m, a_{m+1}, a_{m+2}, \ldots, a_nam,am+1,am+2,…,an , what are aka_kak , kkk , mmm and nnn called?
Term each aka_kak , read " aaa sub kkk " Subscript or index kkk in aka_kak Subscript of the initial term mmm , which may be any integer Subscript of the final term nnn , which must be ≥m\ge m≥m
[Sequences] What is an explicit formula (or general formula) for a sequence?
A rule that shows how the values of aka_kak depend on kkk . Example: ak=kk+1a_k = \frac{k}{k+1}ak=k+1k for all integers k≥1k \ge 1k≥1 gives 12,23,34,…\frac12, \frac23, \frac34, \ldots21,32,43,…
[Sequences] Sequences are defined by ak=kk+1a_k = \frac{k}{k+1}ak=k+1k for all integers k≥1k \ge 1k≥1 and bi=i−1ib_i = \frac{i-1}{i}bi=ii−1 for all integers i≥2i \ge 2i≥2 . How do their terms compare?
The terms are identical: both sequences are 12,23,34,45,56,…\frac12, \frac23, \frac34, \frac45, \frac56, \ldots21,32,43,54,65,… bk+1=(k+1)−1k+1=kk+1=akb_{k+1} = \frac{(k+1)-1}{k+1} = \frac{k}{k+1} = a_kbk+1=k+1(k+1)−1=k+1k=ak . Two different formulas can give the same sequence.
[Sequences] What are the terms of cj=(−1)jc_j = (-1)^jcj=(−1)j for all integers j≥0j \ge 0j≥0 ?
1,−1,1,−1,1,−1,…\boldsymbol{1, -1, 1, -1, 1, -1, \ldots}1,−1,1,−1,1,−1,… Even powers of −1-1−1 equal 1 and odd powers equal −1-1−1 . An infinite sequence can have only finitely many values.
[Sequences] Find an explicit formula aka_kak ( k≥1k \ge 1k≥1 ) for a sequence with initial terms 1,−14,19,−116,125,−136,…1, -\frac14, \frac19, -\frac{1}{16}, \frac{1}{25}, -\frac{1}{36}, \ldots1,−41,91,−161,251,−361,…
ak=(−1)k+1k2\boldsymbol{a_k = \frac{(-1)^{k+1}}{k^2}}ak=k2(−1)k+1 for all integers k≥1k \ge 1k≥1 The denominator of aka_kak is k2k^2k2 . The factor (−1)k+1(-1)^{k+1}(−1)k+1 is +1+1+1 for odd kkk and −1-1−1 for even kkk .Starting from a0a_0a0 instead gives ak=(−1)k(k+1)2a_k = \frac{(-1)^k}{(k+1)^2}ak=(k+1)2(−1)k for k≥0k \ge 0k≥0 .
[Sequences] Does a list of initial terms determine a sequence's explicit formula?
No: two sequences can have the same initial terms and differ later on. So an explicit formula found from initial terms is only a guess.Example: ak=2k+1a_k = 2k + 1ak=2k+1 and bk=(k−1)3+k+2b_k = (k-1)^3 + k + 2bk=(k−1)3+k+2 ( k≥0k \ge 0k≥0 ) both start 1,3,51, 3, 51,3,5 , but a3=7a_3 = 7a3=7 and b3=13b_3 = 13b3=13 .
[Sequences] If m≤nm \le nm≤n are integers, what does ∑k=mnak\displaystyle\sum_{k=m}^{n} a_kk=m∑nak mean, and how is it read?
The sum am+am+1+am+2+⋯+ana_m + a_{m+1} + a_{m+2} + \cdots + a_nam+am+1+am+2+⋯+an , read "the summation from kkk equals mmm to nnn of aaa -sub- kkk ". Example: ∑k=13k=1+2+3=6\displaystyle\sum_{k=1}^{3} k = 1 + 2 + 3 = 6k=1∑3k=1+2+3=6 .
[Sequences] In ∑k=mnak\displaystyle\sum_{k=m}^{n} a_kk=m∑nak , kkk is the index of the summation, mmm the lower limit and nnn the upper limit.
[Sequences] What is the expanded form of ∑k=mnak\displaystyle\sum_{k=m}^{n} a_kk=m∑nak ?
am+am+1+am+2+⋯+an\boldsymbol{a_m + a_{m+1} + a_{m+2} + \cdots + a_n}am+am+1+am+2+⋯+an Example: the expanded form of ∑k=14k2\displaystyle\sum_{k=1}^{4} k^2k=1∑4k2 is 12+22+32+421^2 + 2^2 + 3^2 + 4^212+22+32+42 .
[Sequences] What is a1+a2+a3+⋯+ana_1 + a_2 + a_3 + \cdots + a_na1+a2+a3+⋯+an when n=2n = 2n=2 ?
a1+a2\boldsymbol{a_1 + a_2}a1+a2 The expression is the sum of the terms from a1a_1a1 up to ana_nan ; with n=2n = 2n=2 there is no a3a_3a3 .
[Sequences] Who introduced the capital sigma Σ\SigmaΣ for sums, and when?
Joseph Louis Lagrange, 1772. Σ\SigmaΣ stands for the word sum.
[Sequences] Let a1=−2a_1 = -2a1=−2 , a2=−1a_2 = -1a2=−1 , a3=0a_3 = 0a3=0 , a4=1a_4 = 1a4=1 , a5=2a_5 = 2a5=2 . Compute ∑k=15ak\displaystyle\sum_{k=1}^{5} a_kk=1∑5ak , ∑k=22ak\displaystyle\sum_{k=2}^{2} a_kk=2∑2ak and ∑k=12a2k\displaystyle\sum_{k=1}^{2} a_{2k}k=1∑2a2k .
0\boldsymbol{0}0 , −1\boldsymbol{-1}−1 and 0\boldsymbol{0}0 (−2)+(−1)+0+1+2=0(-2) + (-1) + 0 + 1 + 2 = 0(−2)+(−1)+0+1+2=0 ∑k=22ak=a2=−1\displaystyle\sum_{k=2}^{2} a_k = a_2 = -1k=2∑2ak=a2=−1 ∑k=12a2k=a2⋅1+a2⋅2=a2+a4=−1+1=0\displaystyle\sum_{k=1}^{2} a_{2k} = a_{2 \cdot 1} + a_{2 \cdot 2} = a_2 + a_4 = -1 + 1 = 0k=1∑2a2k=a2⋅1+a2⋅2=a2+a4=−1+1=0
[Sequences] Compute ∑k=15k2\displaystyle\sum_{k=1}^{5} k^2k=1∑5k2 .
55\boldsymbol{55}55 12+22+32+42+52=1+4+9+16+25=551^2 + 2^2 + 3^2 + 4^2 + 5^2 = 1 + 4 + 9 + 16 + 25 = 5512+22+32+42+52=1+4+9+16+25=55
[Sequences] Write ∑i=0n(−1)ii+1\displaystyle\sum_{i=0}^{n} \frac{(-1)^i}{i+1}i=0∑ni+1(−1)i in expanded form.
1−12+13−14+⋯+(−1)nn+1\boldsymbol{1 - \frac12 + \frac13 - \frac14 + \cdots + \frac{(-1)^n}{n+1}}1−21+31−41+⋯+n+1(−1)n (−1)00+1+(−1)11+1+(−1)22+1+(−1)33+1+⋯\frac{(-1)^0}{0+1} + \frac{(-1)^1}{1+1} + \frac{(-1)^2}{2+1} + \frac{(-1)^3}{3+1} + \cdots0+1(−1)0+1+1(−1)1+2+1(−1)2+3+1(−1)3+⋯ . When the upper limit is a variable, the expanded form needs an ellipsis.
[Sequences] Write 1n+2n+1+3n+2+⋯+n+12n\frac{1}{n} + \frac{2}{n+1} + \frac{3}{n+2} + \cdots + \frac{n+1}{2n}n1+n+12+n+23+⋯+2nn+1 in summation notation.
∑k=0nk+1n+k\boldsymbol{\displaystyle\sum_{k=0}^{n} \frac{k+1}{n+k}}k=0∑nn+kk+1 The general term is k+1n+k\frac{k+1}{n+k}n+kk+1 for kkk from 0 to nnn : k=0k = 0k=0 gives 1n\frac1nn1 , k=nk = nk=n gives n+12n\frac{n+1}{2n}2nn+1 .
[Sequences] What is the value of 11⋅2+12⋅3+13⋅4+⋯+1n(n+1)\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + \cdots + \frac{1}{n(n+1)}1⋅21+2⋅31+3⋅41+⋯+n(n+1)1 when n=1n = 1n=1 ?
11⋅2=12\boldsymbol{\frac{1}{1 \cdot 2} = \frac12}1⋅21=21 : the sum has the single term 11⋅2\frac{1}{1 \cdot 2}1⋅21 . Not 11⋅2+12⋅3+13⋅4+⋯\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + \cdots1⋅21+2⋅31+3⋅41+⋯ : the written first terms show only the pattern.Example: n=2n = 2n=2 gives 12+16=23\frac12 + \frac16 = \frac2321+61=32 , and n=3n = 3n=3 gives 12+16+112=34\frac12 + \frac16 + \frac{1}{12} = \frac3421+61+121=43 .
[Sequences] What is the recursive definition of ∑k=mnak\displaystyle\sum_{k=m}^{n} a_kk=m∑nak ( mmm an integer)?
∑k=mmak=am\boldsymbol{\displaystyle\sum_{k=m}^{m} a_k = a_m}k=m∑mak=am and ∑k=mnak=∑k=mn−1ak+an\boldsymbol{\displaystyle\sum_{k=m}^{n} a_k = \sum_{k=m}^{n-1} a_k + a_n}k=m∑nak=k=m∑n−1ak+an for all integers n>mn > mn>m . Example: ∑k=13k=∑k=12k+3=3+3=6\displaystyle\sum_{k=1}^{3} k = \sum_{k=1}^{2} k + 3 = 3 + 3 = 6k=1∑3k=k=1∑2k+3=3+3=6 .
[Sequences] Rewrite ∑i=1n+11i2\displaystyle\sum_{i=1}^{n+1} \frac{1}{i^2}i=1∑n+1i21 by separating off the final term.
∑i=1n1i2+1(n+1)2\boldsymbol{\displaystyle\sum_{i=1}^{n} \frac{1}{i^2} + \frac{1}{(n+1)^2}}i=1∑ni21+(n+1)21
[Sequences] Write ∑k=0n2k+2n+1\displaystyle\sum_{k=0}^{n} 2^k + 2^{n+1}k=0∑n2k+2n+1 as a single summation.
∑k=0n+12k\boldsymbol{\displaystyle\sum_{k=0}^{n+1} 2^k}k=0∑n+12k 2n+12^{n+1}2n+1 is the term with k=n+1k = n + 1k=n+1 .
[Sequences] What is a telescoping sum?
A sum in which each term is a difference of two quantities, so that in the expanded form all quantities cancel except the first and the last. Example: (11−12)+(12−13)+(13−14)=1−14\left(\frac11 - \frac12\right) + \left(\frac12 - \frac13\right) + \left(\frac13 - \frac14\right) = 1 - \frac14(11−21)+(21−31)+(31−41)=1−41 .
[Sequences] 1k−1k+1=1k(k+1)\frac1k - \frac{1}{k+1} = \frac{1}{k(k+1)}k1−k+11=k(k+1)1 Find a simple expression for ∑k=1n1k(k+1)\displaystyle\sum_{k=1}^{n} \frac{1}{k(k+1)}k=1∑nk(k+1)1 .
1−1n+1\boldsymbol{1 - \frac{1}{n+1}}1−n+11 ∑k=1n(1k−1k+1)=(11−12)+(12−13)+⋯+(1n−1n+1)\displaystyle\sum_{k=1}^{n} \left(\frac1k - \frac{1}{k+1}\right) = \left(\frac11 - \frac12\right) + \left(\frac12 - \frac13\right) + \cdots + \left(\frac1n - \frac{1}{n+1}\right)k=1∑n(k1−k+11)=(11−21)+(21−31)+⋯+(n1−n+11) , and all middle fractions cancel.Example: n=3n = 3n=3 : 12+16+112=34=1−14\frac12 + \frac16 + \frac{1}{12} = \frac34 = 1 - \frac1421+61+121=43=1−41 .
[Sequences] If m≤nm \le nm≤n are integers, what does ∏k=mnak\displaystyle\prod_{k=m}^{n} a_kk=m∏nak mean, and how is it read?
The product am⋅am+1⋅am+2⋯ana_m \cdot a_{m+1} \cdot a_{m+2} \cdots a_nam⋅am+1⋅am+2⋯an , read "the product from kkk equals mmm to nnn of aaa -sub- kkk ". Π\PiΠ is the Greek capital letter pi.Example: ∏k=13k=1⋅2⋅3=6\displaystyle\prod_{k=1}^{3} k = 1 \cdot 2 \cdot 3 = 6k=1∏3k=1⋅2⋅3=6 .
[Sequences] What is the recursive definition of ∏k=mnak\displaystyle\prod_{k=m}^{n} a_kk=m∏nak ( mmm an integer)?
∏k=mmak=am\boldsymbol{\displaystyle\prod_{k=m}^{m} a_k = a_m}k=m∏mak=am and ∏k=mnak=(∏k=mn−1ak)⋅an\boldsymbol{\displaystyle\prod_{k=m}^{n} a_k = \left(\prod_{k=m}^{n-1} a_k\right) \cdot a_n}k=m∏nak=(k=m∏n−1ak)⋅an for all integers n>mn > mn>m . Example: ∏k=13k=(∏k=12k)⋅3=2⋅3=6\displaystyle\prod_{k=1}^{3} k = \left(\prod_{k=1}^{2} k\right) \cdot 3 = 2 \cdot 3 = 6k=1∏3k=(k=1∏2k)⋅3=2⋅3=6 .
[Sequences] Compute ∏k=15k\displaystyle\prod_{k=1}^{5} kk=1∏5k and ∏k=11kk+1\displaystyle\prod_{k=1}^{1} \frac{k}{k+1}k=1∏1k+1k .
120\boldsymbol{120}120 and 12\boldsymbol{\frac12}21 1⋅2⋅3⋅4⋅5=1201 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 1201⋅2⋅3⋅4⋅5=120 A product with one factor: 11+1=12\frac{1}{1+1} = \frac121+11=21 .
[Sequences] am,am+1,…a_m, a_{m+1}, \ldotsam,am+1,… and bm,bm+1,…b_m, b_{m+1}, \ldotsbm,bm+1,… are sequences of real numbers, ccc is a real number and n≥mn \ge mn≥m . Which three properties of sums and products hold?
Sum of sums ∑k=mnak+∑k=mnbk=∑k=mn(ak+bk)\displaystyle\sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k = \sum_{k=m}^{n} (a_k + b_k)k=m∑nak+k=m∑nbk=k=m∑n(ak+bk) Example: (1+2)+(1+4)=(1+1)+(2+4)=8(1 + 2) + (1 + 4) = (1 + 1) + (2 + 4) = 8(1+2)+(1+4)=(1+1)+(2+4)=8 for ak=ka_k = kak=k , bk=k2b_k = k^2bk=k2 , k=1,2k = 1, 2k=1,2 . Generalized distributive law c⋅∑k=mnak=∑k=mnc⋅ak\displaystyle c \cdot \sum_{k=m}^{n} a_k = \sum_{k=m}^{n} c \cdot a_kc⋅k=m∑nak=k=m∑nc⋅ak Example: 3⋅(1+2)=3+6=93 \cdot (1…
[Sequences] Write ∑k=mnak+c⋅∑k=mnbk\displaystyle\sum_{k=m}^{n} a_k + c \cdot \sum_{k=m}^{n} b_kk=m∑nak+c⋅k=m∑nbk as a single summation.
∑k=mn(ak+c bk)\boldsymbol{\displaystyle\sum_{k=m}^{n} (a_k + c \, b_k)}k=m∑n(ak+cbk) First c⋅∑bk=∑c bkc \cdot \sum b_k = \sum c \, b_kc⋅∑bk=∑cbk (generalized distributive law), then add the two sums termwise.
[Sequences] Let ak=k+1a_k = k + 1ak=k+1 and bk=k−1b_k = k - 1bk=k−1 . Write ∑k=mnak+2⋅∑k=mnbk\displaystyle\sum_{k=m}^{n} a_k + 2 \cdot \sum_{k=m}^{n} b_kk=m∑nak+2⋅k=m∑nbk as a single summation and (∏k=mnak)⋅(∏k=mnbk)\displaystyle\left(\prod_{k=m}^{n} a_k\right) \cdot \left(\prod_{k=m}^{n} b_k\right)(k=m∏nak)⋅(k=m∏nbk) as a single product.
∑k=mn(3k−1)\boldsymbol{\displaystyle\sum_{k=m}^{n} (3k - 1)}k=m∑n(3k−1) and ∏k=mn(k2−1)\boldsymbol{\displaystyle\prod_{k=m}^{n} (k^2 - 1)}k=m∏n(k2−1) (k+1)+2(k−1)=3k−1(k + 1) + 2(k - 1) = 3k - 1(k+1)+2(k−1)=3k−1 and (k+1)(k−1)=k2−1(k + 1)(k - 1) = k^2 - 1(k+1)(k−1)=k2−1 .
[Sequences] What is a dummy variable?
A symbol that derives its entire meaning from its local context. Outside that context the symbol may have another meaning. The index of a summation is a dummy variable: it can be replaced by any other symbol in every place it occurs.Example: ∑k=13k2=∑i=13i2=12+22+32\displaystyle\sum_{k=1}^{3} k^2 = \sum_{i=1}^{3} i^2 = 1^2 + 2^2 + 3^2k=1∑3k2=i=1∑3i2=12+22+32 .
[Sequences] How do you transform ∑k=061k+1\displaystyle\sum_{k=0}^{6} \frac{1}{k+1}k=0∑6k+11 by the change of variable j=k+1j = k + 1j=k+1 ?
∑j=171j\boldsymbol{\displaystyle\sum_{j=1}^{7} \frac1j}j=1∑7j1 New limits: k=0k = 0k=0 gives j=1j = 1j=1 , and k=6k = 6k=6 gives j=7j = 7j=7 .New general term: k=j−1k = j - 1k=j−1 , so 1k+1=1(j−1)+1=1j\frac{1}{k+1} = \frac{1}{(j-1)+1} = \frac1jk+11=(j−1)+11=j1 .Since jjj is a dummy variable, this also equals ∑k=171k\displaystyle\sum_{k=1}^{7} \frac1kk=1∑7k1 .
[Sequences] Transform ∑k=1n+1kn+k\displaystyle\sum_{k=1}^{n+1} \frac{k}{n+k}k=1∑n+1n+kk by the change of variable j=k−1j = k - 1j=k−1 , then rename jjj to kkk .
∑k=0nk+1n+(k+1)\boldsymbol{\displaystyle\sum_{k=0}^{n} \frac{k+1}{n+(k+1)}}k=0∑nn+(k+1)k+1 k=1k = 1k=1 gives j=0j = 0j=0 , and k=n+1k = n + 1k=n+1 gives j=nj = nj=n . With k=j+1k = j + 1k=j+1 : kn+k=j+1n+(j+1)\frac{k}{n+k} = \frac{j+1}{n+(j+1)}n+kk=n+(j+1)j+1 . Here nnn is a constant: only kkk is replaced.Example: n=1n = 1n=1 : both sides equal 12+23\frac12 + \frac2321+32 .
[Sequences] For a positive integer nnn , what is nnn factorial n!n!n! , and what is 0!0!0! ?
n!=n⋅(n−1)⋯3⋅2⋅1\boldsymbol{n! = n \cdot (n-1) \cdots 3 \cdot 2 \cdot 1}n!=n⋅(n−1)⋯3⋅2⋅1 , and 0!=1\boldsymbol{0! = 1}0!=1 . 0!=10! = 10!=1 makes many formulas work, e.g. the formula for (nr)\binom{n}{r}(rn) .Example: 4!=4⋅3⋅2⋅1=244! = 4 \cdot 3 \cdot 2 \cdot 1 = 244!=4⋅3⋅2⋅1=24 , 5!=1205! = 1205!=120 , 6!=7206! = 7206!=720 , 7!=50407! = 50407!=5040 .
[Sequences] What is the recursive definition of n!n!n! for nonnegative integers nnn ?
0!=1\boldsymbol{0! = 1}0!=1 and n!=n⋅(n−1)!\boldsymbol{n! = n \cdot (n-1)!}n!=n⋅(n−1)! for n≥1n \ge 1n≥1 . n⋅(n−1)!n \cdot (n-1)!n⋅(n−1)! means n⋅[(n−1)!]n \cdot [(n-1)!]n⋅[(n−1)!] , not [n⋅(n−1)]![n \cdot (n-1)]![n⋅(n−1)]! .Example: 5!=5⋅4!=5⋅24=1205! = 5 \cdot 4! = 5 \cdot 24 = 1205!=5⋅4!=5⋅24=120 .
[Sequences] Simplify 8!7!\frac{8!}{7!}7!8! , (n+1)!n!\frac{(n+1)!}{n!}n!(n+1)! and n!(n−3)!\frac{n!}{(n-3)!}(n−3)!n! .
8\boldsymbol{8}8 , n+1\boldsymbol{n + 1}n+1 and n(n−1)(n−2)\boldsymbol{n(n-1)(n-2)}n(n−1)(n−2) Write the larger factorial using the recursive definition and cancel: 8⋅7!7!=8\frac{8 \cdot 7!}{7!} = 87!8⋅7!=8 , (n+1)⋅n!n!=n+1\ \frac{(n+1) \cdot n!}{n!} = n + 1 n!(n+1)⋅n!=n+1 , n(n−1)(n−2)⋅(n−3)!(n−3)!=n3−3n2+2n\ \frac{n(n-1)(n-2) \cdot (n-3)!}{(n-3)!} = n^3 - 3n^2 + 2n (n−3)!n(n−1)(n−2)⋅(n−3)!=n3−3n2+2n .
[Sequences] Compute 12!⋅4!+13!⋅3!\frac{1}{2! \cdot 4!} + \frac{1}{3! \cdot 3!}2!⋅4!1+3!⋅3!1 .
7144\boldsymbol{\frac{7}{144}}1447 Common denominator 3!⋅4!3! \cdot 4!3!⋅4! : 33⋅2!⋅4!+43!⋅4⋅3!=33!⋅4!+43!⋅4!=76⋅24\frac{3}{3 \cdot 2! \cdot 4!} + \frac{4}{3! \cdot 4 \cdot 3!} = \frac{3}{3! \cdot 4!} + \frac{4}{3! \cdot 4!} = \frac{7}{6 \cdot 24}3⋅2!⋅4!3+3!⋅4⋅3!4=3!⋅4!3+3!⋅4!4=6⋅247 .
[Sequences] For integers 0≤r≤n0 \le r \le n0≤r≤n , what does (nr)\binom{n}{r}(rn) (" nnn choose rrr ") represent?
The number of subsets of size rrr that can be chosen from a set with nnn elements. So (nr)\binom{n}{r}(rn) is always an integer.Example: (42)=6\binom42 = 6(24)=6 : the 2-element subsets of {a,b,c,d}\{a, b, c, d\}{a,b,c,d} are {a,b},{a,c},{a,d},{b,c},{b,d},{c,d}\{a,b\}, \{a,c\}, \{a,d\}, \{b,c\}, \{b,d\}, \{c,d\}{a,b},{a,c},{a,d},{b,c},{b,d},{c,d} .
[Sequences] What is the formula for computing (nr)\binom{n}{r}(rn) ( 0≤r≤n0 \le r \le n0≤r≤n )?
(nr)=n!r! (n−r)!\boldsymbol{\binom{n}{r} = \frac{n!}{r!\,(n-r)!}}(rn)=r!(n−r)!n! Since (nr)\binom{n}{r}(rn) is an integer, all factors of the denominator cancel against factors of the numerator. Cancel before multiplying.Example: (85)=8!5!⋅3!=8⋅7⋅63⋅2⋅1=56\binom85 = \frac{8!}{5! \cdot 3!} = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 56(58)=5!⋅3!8!=3⋅2⋅18⋅7⋅6=56 .
[Sequences] The numbers (nr)\binom{n}{r}(rn) , also written C(n,r)C(n, r)C(n,r) , are also called combinations or binomial coefficients.
Other notations: nCrnCrnCr , nCr^{n}C_rnCr , Cn,rC_{n,r}Cn,r . "Binomial coefficients" refers to the binomial theorem.
[Sequences] Compute (44)\binom44(44) and (n+1n)\binom{n+1}{n}(nn+1) with the formula (nr)=n!r! (n−r)!\binom{n}{r} = \frac{n!}{r!\,(n-r)!}(rn)=r!(n−r)!n! .
1\boldsymbol{1}1 and n+1\boldsymbol{n + 1}n+1 4!4!⋅0!=1\frac{4!}{4! \cdot 0!} = 14!⋅0!4!=1 : here 0!=10! = 10!=1 makes the formula computable, and a 4-set has exactly one subset of size 4. (n+1)!n!⋅1!=(n+1)⋅n!n!=n+1\frac{(n+1)!}{n! \cdot 1!} = \frac{(n+1) \cdot n!}{n!} = n + 1n!⋅1!(n+1)!=n!(n+1)⋅n!=n+1
[Sequences] In computer programming, what is a one-dimensional array?
A finite sequence, with subscripts written in square brackets. Example: 50 wages stored as W[1],W[2],…,W[50]W[1], W[2], \ldots, W[50]W[1],W[2],…,W[50] .
[Sequences] Do these three loops print the same output? for i:=1i := 1i:=1 to nnn : print a[i]a[i]a[i] for j:=0j := 0j:=0 to n−1n - 1n−1 : print a[j+1]a[j+1]a[j+1] for k:=2k := 2k:=2 to n+1n + 1n+1 : print a[k−1]a[k-1]a[k−1]
Yes: each prints a[1],a[2],…,a[n]a[1], a[2], \ldots, a[n]a[1],a[2],…,a[n] . The index variable of a for-next loop is a dummy variable, like the index of a summation.
[Sequences] Give two loops that compute ∑k=1na[k]\displaystyle\sum_{k=1}^{n} a[k]k=1∑na[k] , one following the recursive definition of summation.
s:=a[1]\boldsymbol{s := a[1]}s:=a[1] , for k:=2k := 2k:=2 to nnn : s:=s+a[k]s := s + a[k]s:=s+a[k] ; or s:=0\boldsymbol{s := 0}s:=0 , for k:=1k := 1k:=1 to nnn : s:=s+a[k]s := s + a[k]s:=s+a[k] . The first loop follows ∑k=11a[k]=a[1]\sum_{k=1}^{1} a[k] = a[1]∑k=11a[k]=a[1] and ∑k=1ma[k]=∑k=1m−1a[k]+a[m]\sum_{k=1}^{m} a[k] = \sum_{k=1}^{m-1} a[k] + a[m]∑k=1ma[k]=∑k=1m−1a[k]+a[m] .
[Sequences] How does repeated division by 2 convert a nonnegative integer aaa to binary notation?
Divide aaa by 2, then each quotient by 2, until the quotient is 0; the remainders r[0],r[1],…,r[k]r[0], r[1], \ldots, r[k]r[0],r[1],…,r[k] read from last to first are the binary digits: a=(r[k]⋯r[1]r[0])2a = (r[k] \cdots r[1] r[0])_2a=(r[k]⋯r[1]r[0])2 . Each remainder is 0 or 1, because the divisor is 2. Example: 3810=100110238_{10} = 100110_23810=1001102 (read the divisions from the bottom up).
[Sequences] Repeated division by 2: a=q[0]⋅2+r[0]a = q[0] \cdot 2 + r[0]a=q[0]⋅2+r[0] , q[0]=q[1]⋅2+r[1]q[0] = q[1] \cdot 2 + r[1]q[0]=q[1]⋅2+r[1] , and so on until a quotient is 0.Why are the remainders r[k],…,r[0]r[k], \ldots, r[0]r[k],…,r[0] the binary digits of aaa ?
Substituting each equation into the previous one gives a=2k⋅r[k]+2k−1⋅r[k−1]+⋯+21⋅r[1]+20⋅r[0]a = 2^k \cdot r[k] + 2^{k-1} \cdot r[k-1] + \cdots + 2^1 \cdot r[1] + 2^0 \cdot r[0]a=2k⋅r[k]+2k−1⋅r[k−1]+⋯+21⋅r[1]+20⋅r[0] , with every r[i]r[i]r[i] equal to 0 or 1. Example: 38=19⋅2+0=(9⋅2+1)⋅2+0=9⋅22+1⋅2+0=⋯=1⋅25+0⋅24+0⋅23+1⋅22+1⋅2+038 = 19 \cdot 2 + 0 = (9 \cdot 2 + 1) \cdot 2 + 0 = 9 \cdot 2^2 + 1 \cdot 2 + 0 = \cdots = 1 \cdot 2^5 + 0 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2 + 038=19⋅2+0…
[Sequences] Use repeated division by 2 to write 291029_{10}2910 in binary notation.
111012\boldsymbol{11101_2}111012 29=14⋅2+129 = 14 \cdot 2 + 129=14⋅2+1 , 14=7⋅2+014 = 7 \cdot 2 + 014=7⋅2+0 , 7=3⋅2+17 = 3 \cdot 2 + 17=3⋅2+1 , 3=1⋅2+13 = 1 \cdot 2 + 13=1⋅2+1 , 1=0⋅2+11 = 0 \cdot 2 + 11=0⋅2+1 . Check: 16+8+4+1=2916 + 8 + 4 + 1 = 2916+8+4+1=29 .
[Sequences] What is the loop of the algorithm decimal to binary conversion using repeated division by 2 (input: nonnegative integer nnn ; start with q:=nq := nq:=n , i:=0i := 0i:=0 )?
while (i=0 or q≠0)\boldsymbol{(i = 0 \text{ or } q \ne 0)}(i=0 or q=0) : r[i]:=q mod 2\boldsymbol{r[i] := q \bmod 2}r[i]:=qmod2 , q:=qdiv⁡2\boldsymbol{q := q \operatorname{div} 2}q:=qdiv2 , i:=i+1\boldsymbol{i := i + 1}i:=i+1 Output: r[0],r[1],…,r[i−1]r[0], r[1], \ldots, r[i-1]r[0],r[1],…,r[i−1] , with n=(r[i−1]⋯r[1]r[0])2n = (r[i-1] \cdots r[1] r[0])_2n=(r[i−1]⋯r[1]r[0])2 .Example: n=6n = 6n=6 : r[0]=0r[0] = 0r[0]=0 , q=3q = 3q=3 ; r[1]=1r[1] = 1r[1]=1 , q=1q = 1q=1 ; r[2]=1r[2] = 1r[2]=1 ,…
[Sequences] Decimal to binary: q:=nq := nq:=n , i:=0i := 0i:=0 ; while (i=0 or q≠0)(i = 0 \text{ or } q \ne 0)(i=0 or q=0) : r[i]:=q mod 2r[i] := q \bmod 2r[i]:=qmod2 , q:=qdiv⁡2q := q \operatorname{div} 2q:=qdiv2 , i:=i+1i := i + 1i:=i+1 .Why does the guard condition contain " i=0i = 0i=0 or"?
So that the loop runs at least once, even for input n=0n = 0n=0 , and computes r[0]=0r[0] = 0r[0]=0 . With only q≠0q \ne 0q=0 , input 0 would produce no digits.
[Mathematical Induction I] Using only 3¢ and 5¢ coins, which whole amounts of cents (at least 1¢) can not be paid with exact change?
1¢, 2¢, 4¢ and 7¢. Every amount nnn ¢ with n≥8n \ge 8n≥8 can be obtained: 8=3+58 = 3 + 58=3+5 , 9=3+3+39 = 3 + 3 + 39=3+3+3 , 10=5+510 = 5 + 510=5+5 , …
[Mathematical Induction I] Claim: for all integers n≥8n \ge 8n≥8 , nnn ¢ can be obtained using 3¢ and 5¢ coins.Inductive step: kkk ¢ ( k≥8k \ge 8k≥8 ) is obtained with at least one 5¢ coin. How do you obtain (k+1)(k+1)(k+1) ¢?
Replace one 5¢ coin by two 3¢ coins. −5+3+3=+1-5 + 3 + 3 = +1−5+3+3=+1
[Mathematical Induction I] Claim: for all integers n≥8n \ge 8n≥8 , nnn ¢ can be obtained using 3¢ and 5¢ coins.Inductive step: kkk ¢ ( k≥8k \ge 8k≥8 ) is obtained without any 5¢ coin. How do you obtain (k+1)(k+1)(k+1) ¢?
Replace three 3¢ coins by two 5¢ coins. There are at least three 3¢ coins because k≥8k \ge 8k≥8 and only 3¢ coins are used. −9+10=+1-9 + 10 = +1−9+10=+1 .
[Mathematical Induction I] What is mathematical induction?
A method for proving that a property defined for integers nnn is true for all values of nnn that are greater than or equal to some initial integer. Example: proving that 1+2+⋯+n=n(n+1)21 + 2 + \cdots + n = \frac{n(n+1)}{2}1+2+⋯+n=2n(n+1) for all integers n≥1n \ge 1n≥1 .
[Mathematical Induction I] State the principle of mathematical induction for a property P(n)P(n)P(n) defined for integers nnn and a fixed integer aaa .
If P(a)P(a)P(a) is true, and for all integers k≥ak \ge ak≥a , P(k)P(k)P(k) true implies P(k+1)P(k+1)P(k+1) true, then P(n)P(n)P(n) is true for all integers n≥an \ge an≥a . Example: P(8)P(8)P(8) and " P(k)⇒P(k+1)P(k) \Rightarrow P(k+1)P(k)⇒P(k+1) for all k≥8k \ge 8k≥8 " give P(8),P(9),P(10),…P(8), P(9), P(10), \ldotsP(8),P(9),P(10),…
[Mathematical Induction I] How do falling dominoes illustrate mathematical induction?
If the kkk th domino falls it pushes the (k+1)(k+1)(k+1) st, and the first domino falls; so every domino falls. P(n)P(n)P(n) = "the nnn th domino falls backward": P(1)P(1)P(1) is true, and P(k)⇒P(k+1)P(k) \Rightarrow P(k+1)P(k)⇒P(k+1) for each k≥1k \ge 1k≥1 .
[Mathematical Induction I] Where does the first known use of mathematical induction occur, and who gave the method its name?
Francesco Maurolico, 1575; Augustus De Morgan named it in 1883. In the 17th century Fermat and Pascal used the technique; Fermat called it the "method of infinite descent".
[Mathematical Induction I] Why is it called the principle of mathematical induction rather than a theorem?
Its validity is generally taken as an axiom.
[Mathematical Induction I] State the principle of mathematical induction as a property of sets of integers.
If SSS is a set of integers with a∈Sa \in Sa∈S , and for all integers k≥ak \ge ak≥a , k∈Sk \in Sk∈S implies k+1∈Sk + 1 \in Sk+1∈S , then SSS contains every integer ≥a\ge a≥a . Take SSS = the set of integers nnn for which P(n)P(n)P(n) is true to get the usual form.
[Mathematical Induction I] What are the two steps of a proof by mathematical induction of "for all integers n≥an \ge an≥a , P(n)P(n)P(n) "?
Basis step Show that P(a)P(a)P(a) is true. Example: for 1+2+⋯+n=n(n+1)21 + 2 + \cdots + n = \frac{n(n+1)}{2}1+2+⋯+n=2n(n+1) , show 1=1⋅221 = \frac{1 \cdot 2}{2}1=21⋅2 . Inductive step Suppose P(k)P(k)P(k) is true for a particular but arbitrarily chosen integer k≥ak \ge ak≥a , and show that P(k+1)P(k+1)P(k+1) is true. Example: from 1+⋯+k=k(k+1)21 + \cdots + k = \frac{k(k+1)}{2}1+⋯+k=2k(k+1) , show 1+⋯+(k+1)=(k+1)(k+2)21 + \cdots + (k+1) = \frac{(k+1)(k+2)}{2}1+⋯+(k+1)=2(k+1)(k+2) .
[Mathematical Induction I] In the inductive step, the supposition that P(k)P(k)P(k) is true for a particular but arbitrarily chosen integer k≥ak \ge ak≥a is called the inductive hypothesis.
[Mathematical Induction I] What is the formula for the sum of the first nnn integers, 1+2+⋯+n1 + 2 + \cdots + n1+2+⋯+n ( n≥1n \ge 1n≥1 )?
n(n+1)2\boldsymbol{\frac{n(n+1)}{2}}2n(n+1) Example: 1+2+3+4=10=4⋅521 + 2 + 3 + 4 = 10 = \frac{4 \cdot 5}{2}1+2+3+4=10=24⋅5 .
[Mathematical Induction I] P(n)P(n)P(n) is the equation 1+2+⋯+n=n(n+1)21 + 2 + \cdots + n = \frac{n(n+1)}{2}1+2+⋯+n=2n(n+1) .How do you write P(k+1)P(k+1)P(k+1) ?
Replace each nnn in P(n)P(n)P(n) by k+1k + 1k+1 : 1+2+⋯+(k+1)=(k+1)(k+2)2\boldsymbol{1 + 2 + \cdots + (k+1) = \frac{(k+1)(k+2)}{2}}1+2+⋯+(k+1)=2(k+1)(k+2) (k+1)((k+1)+1)2=(k+1)(k+2)2\frac{(k+1)((k+1)+1)}{2} = \frac{(k+1)(k+2)}{2}2(k+1)((k+1)+1)=2(k+1)(k+2)
[Mathematical Induction I] Inductive hypothesis: 1+2+⋯+k=k(k+1)21 + 2 + \cdots + k = \frac{k(k+1)}{2}1+2+⋯+k=2k(k+1) .How does the inductive step show 1+2+⋯+(k+1)=(k+1)(k+2)21 + 2 + \cdots + (k+1) = \frac{(k+1)(k+2)}{2}1+2+⋯+(k+1)=2(k+1)(k+2) ?
Split off the last term and substitute: (1+⋯+k)+(k+1)=k(k+1)2+(k+1)(1 + \cdots + k) + (k+1) = \frac{k(k+1)}{2} + (k+1)(1+⋯+k)+(k+1)=2k(k+1)+(k+1) , which equals k2+3k+22\frac{k^2 + 3k + 2}{2}2k2+3k+2 , as does the right-hand side. k(k+1)2+2(k+1)2=k2+k+2k+22\frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{k^2 + k + 2k + 2}{2}2k(k+1)+22(k+1)=2k2+k+2k+2 and (k+1)(k+2)2=k2+3k+22\frac{(k+1)(k+2)}{2} = \frac{k^2 + 3k + 2}{2}2(k+1)(k+2)=2k2+3k+2 .
[Mathematical Induction I] How could the young Carl Friedrich Gauss (1777–1855) compute 1+2+⋯+1001 + 2 + \cdots + 1001+2+⋯+100 in a few moments?
He paired the numbers into 50 pairs, each with sum 101, so the total is 50⋅101=505050 \cdot 101 = 505050⋅101=5050 . 1+1001 + 1001+100 , 2+992 + 992+99 , …, 50+5150 + 5150+51
[Mathematical Induction I] When is a sum with a variable number of terms written in closed form?
When it is shown equal to a formula that contains neither an ellipsis nor a summation symbol. Example: 1+2+⋯+n=n(n+1)21 + 2 + \cdots + n = \frac{n(n+1)}{2}1+2+⋯+n=2n(n+1) writes 1+2+⋯+n1 + 2 + \cdots + n1+2+⋯+n in closed form.
[Mathematical Induction I] 1+2+⋯+n=n(n+1)21 + 2 + \cdots + n = \frac{n(n+1)}{2}1+2+⋯+n=2n(n+1) for all integers n≥1n \ge 1n≥1 .Evaluate 2+4+6+⋯+5002 + 4 + 6 + \cdots + 5002+4+6+⋯+500 and 5+6+7+⋯+505 + 6 + 7 + \cdots + 505+6+7+⋯+50 .
62,750\boldsymbol{62{,}750}62,750 and 1265\boldsymbol{1265}1265 2(1+2+⋯+250)=2⋅250⋅2512=62,7502(1 + 2 + \cdots + 250) = 2 \cdot \frac{250 \cdot 251}{2} = 62{,}7502(1+2+⋯+250)=2⋅2250⋅251=62,750 (1+⋯+50)−(1+2+3+4)=50⋅512−10=1265(1 + \cdots + 50) - (1 + 2 + 3 + 4) = \frac{50 \cdot 51}{2} - 10 = 1265(1+⋯+50)−(1+2+3+4)=250⋅51−10=1265
[Mathematical Induction I] For an integer h≥2h \ge 2h≥2 , write 1+2+3+⋯+(h−1)1 + 2 + 3 + \cdots + (h-1)1+2+3+⋯+(h−1) in closed form.
(h−1)h2\boldsymbol{\frac{(h-1)h}{2}}2(h−1)h The formula n(n+1)2\frac{n(n+1)}{2}2n(n+1) with n=h−1n = h - 1n=h−1 : (h−1)((h−1)+1)2\frac{(h-1)((h-1)+1)}{2}2(h−1)((h−1)+1) .
[Mathematical Induction I] What is a geometric sequence?
A sequence in which each term is obtained from the preceding one by multiplying by a constant factor. Example: first term 1 and factor rrr : 1,r,r2,r3,…1, r, r^2, r^3, \ldots1,r,r2,r3,… ; with r=3r = 3r=3 : 1,3,9,27,…1, 3, 9, 27, \ldots1,3,9,27,…
[Mathematical Induction I] Sum of a geometric sequence: for any real number r≠1r \ne 1r=1 and any integer n≥0n \ge 0n≥0 , ∑i=0nri= ?\displaystyle\sum_{i=0}^{n} r^i = \; ?i=0∑nri=?
rn+1−1r−1\boldsymbol{\frac{r^{n+1} - 1}{r - 1}}r−1rn+1−1 Example: 1+2+4+8=15=24−12−11 + 2 + 4 + 8 = 15 = \frac{2^4 - 1}{2 - 1}1+2+4+8=15=2−124−1 .
[Mathematical Induction I] P(n)P(n)P(n) : ∑i=0nri=rn+1−1r−1\displaystyle\sum_{i=0}^{n} r^i = \frac{r^{n+1} - 1}{r - 1}i=0∑nri=r−1rn+1−1 , for a fixed real r≠1r \ne 1r=1 .Why is the basis step P(0)P(0)P(0) true?
Both sides equal 1: the left side is r0=1r^0 = 1r0=1 , and the right side is r1−1r−1=1\frac{r^1 - 1}{r - 1} = 1r−1r1−1=1 because r≠1r \ne 1r=1 .
[Mathematical Induction I] Inductive hypothesis: ∑i=0kri=rk+1−1r−1\displaystyle\sum_{i=0}^{k} r^i = \frac{r^{k+1} - 1}{r - 1}i=0∑kri=r−1rk+1−1 , with r≠1r \ne 1r=1 .How does the inductive step show ∑i=0k+1ri=rk+2−1r−1\displaystyle\sum_{i=0}^{k+1} r^i = \frac{r^{k+2} - 1}{r - 1}i=0∑k+1ri=r−1rk+2−1 ?
Separate off the term rk+1r^{k+1}rk+1 and substitute: rk+1−1r−1+rk+1\frac{r^{k+1} - 1}{r - 1} + r^{k+1}r−1rk+1−1+rk+1 , then add the fractions. =rk+1−1+rk+1(r−1)r−1=rk+1−1+rk+2−rk+1r−1=rk+2−1r−1= \frac{r^{k+1} - 1 + r^{k+1}(r - 1)}{r - 1} = \frac{r^{k+1} - 1 + r^{k+2} - r^{k+1}}{r - 1} = \frac{r^{k+2} - 1}{r - 1}=r−1rk+1−1+rk+1(r−1)=r−1rk+1−1+rk+2−rk+1=r−1rk+2−1
[Mathematical Induction I] What are two valid ways to show that an equation is true?
Transform both sides separately Transform the left-hand side and the right-hand side independently until they are seen to be equal. Example: both sides of 1+⋯+(k+1)=(k+1)(k+2)21 + \cdots + (k+1) = \frac{(k+1)(k+2)}{2}1+⋯+(k+1)=2(k+1)(k+2) become k2+3k+22\frac{k^2 + 3k + 2}{2}2k2+3k+2 . Transform one side into the other Transform one side step by step until it is the same as the other side. Example: ∑i=0k+1ri\sum_{i=0}^{k+1} r^i∑i=0k+1ri is transformed into rk+2−1r−1\frac{r^{k+2} - 1}{r - 1}r…
[Mathematical Induction I] Why is it invalid to prove an equation by deducing a true statement (such as 1=11 = 11=1 ) from it?
A true conclusion can also be deduced from a false statement, so deducing it proves nothing about the starting equation. Example: 1=01 = 01=0 , so 0=10 = 10=1 , so 1+0=0+11 + 0 = 0 + 11+0=0+1 , so 1=11 = 11=1 .
[Mathematical Induction I] 1+r+r2+⋯+rn=rn+1−1r−11 + r + r^2 + \cdots + r^n = \frac{r^{n+1} - 1}{r - 1}1+r+r2+⋯+rn=r−1rn+1−1 for real r≠1r \ne 1r=1 and integers n≥0n \ge 0n≥0 .For an integer m≥3m \ge 3m≥3 , write 1+3+32+⋯+3m−21 + 3 + 3^2 + \cdots + 3^{m-2}1+3+32+⋯+3m−2 and 32+33+⋯+3m3^2 + 3^3 + \cdots + 3^m32+33+⋯+3m in closed form.
3m−1−12\boldsymbol{\frac{3^{m-1} - 1}{2}}23m−1−1 and 9⋅3m−1−12\boldsymbol{9 \cdot \frac{3^{m-1} - 1}{2}}9⋅23m−1−1 First sum: r=3r = 3r=3 , n=m−2n = m - 2n=m−2 . Second sum: factor out 323^232 to get 32⋅(1+3+⋯+3m−2)3^2 \cdot (1 + 3 + \cdots + 3^{m-2})32⋅(1+3+⋯+3m−2) .Example: m=3m = 3m=3 : 1+3=4=9−121 + 3 = 4 = \frac{9 - 1}{2}1+3=4=29−1 and 9+27=36=9⋅49 + 27 = 36 = 9 \cdot 49+27=36=9⋅4 .
[Mathematical Induction I] With Sn=1+r+r2+⋯+rnS_n = 1 + r + r^2 + \cdots + r^nSn=1+r+r2+⋯+rn , how does computing rSn−SnrS_n - S_nrSn−Sn give the formula for SnS_nSn ( r≠1r \ne 1r=1 )?
rSn−Sn=rn+1−1rS_n - S_n = r^{n+1} - 1rSn−Sn=rn+1−1 (all other terms cancel), and rSn−Sn=(r−1)SnrS_n - S_n = (r-1)S_nrSn−Sn=(r−1)Sn , so Sn=rn+1−1r−1S_n = \frac{r^{n+1} - 1}{r - 1}Sn=r−1rn+1−1 . rSn=r+r2+⋯+rn+1rS_n = r + r^2 + \cdots + r^{n+1}rSn=r+r2+⋯+rn+1
[Mathematical Induction I] Derivation: rSn−Sn=(r+r2+⋯+rn+1)−(1+r+⋯+rn)=rn+1−1rS_n - S_n = (r + r^2 + \cdots + r^{n+1}) - (1 + r + \cdots + r^n) = r^{n+1} - 1rSn−Sn=(r+r2+⋯+rn+1)−(1+r+⋯+rn)=rn+1−1 .Why is this derivation less airtight than a proof by mathematical induction?
The claim that the terms hidden in the ellipsis cancel cannot be fully checked, while induction verifies exactly what happens in the middle of the ellipsis.
[Mathematical Induction II] In the natural sciences, "induction" means stating a general principle after observing many instances. Mathematical induction is not that: it is a form of deductive reasoning.
A theorem proved by mathematical induction is known as certainly as one proved by any other mathematical method.
[Mathematical Induction II] In mathematics, inductive reasoning (observing a pattern in many cases) is used only to make conjectures; mathematical induction is then used to prove them.
Example: (1−12)=12\left(1 - \frac12\right) = \frac12(1−21)=21 , (1−12)(1−13)=13\left(1 - \frac12\right)\left(1 - \frac13\right) = \frac13(1−21)(1−31)=31 , (1−12)(1−13)(1−14)=14\left(1 - \frac12\right)\left(1 - \frac13\right)\left(1 - \frac14\right) = \frac14(1−21)(1−31)(1−41)=41 suggests the conjecture that the product up to (1−1n)\left(1 - \frac1n\right)(1−n1) is 1n\frac1nn1 .
[Mathematical Induction II] Suppose (1−12)(1−13)⋯(1−1k)=1k\left(1 - \frac12\right)\left(1 - \frac13\right)\cdots\left(1 - \frac1k\right) = \frac1k(1−21)(1−31)⋯(1−k1)=k1 . Why does the product up to (1−1k+1)\left(1 - \frac{1}{k+1}\right)(1−k+11) then equal 1k+1\frac{1}{k+1}k+11 ?
Multiply by the next factor: 1k(1−1k+1)=1k⋅kk+1=1k+1\displaystyle \frac1k\left(1 - \frac{1}{k+1}\right) = \frac1k \cdot \frac{k}{k+1} = \boldsymbol{\frac{1}{k+1}}k1(1−k+11)=k1⋅k+1k=k+11 This inductive step is what turns the observed pattern into a theorem: it shows why each case follows from the one before.
[Mathematical Induction II] Prove by induction: 22n−12^{2n} - 122n−1 is divisible by 3 for all integers n≥0n \ge 0n≥0 . What is the basis step?
P(0)P(0)P(0) : 22⋅0−1=1−1=0=3⋅02^{2 \cdot 0} - 1 = 1 - 1 = 0 = 3 \cdot 022⋅0−1=1−1=0=3⋅0 , so it is divisible by 3. P(n)P(n)P(n) is the sentence " 22n−12^{2n} - 122n−1 is divisible by 3".
[Mathematical Induction II] Claim: 22n−12^{2n} - 122n−1 is divisible by 3 for all integers n≥0n \ge 0n≥0 . Inductive hypothesis: 22k−1=3r2^{2k} - 1 = 3r22k−1=3r for some integer rrr .How does the inductive step show that 22(k+1)−12^{2(k+1)} - 122(k+1)−1 is divisible by 3?
Write it as a multiple of 3 plus the old quantity: 22(k+1)−1=22k⋅3+(22k−1)=3(22k+r)2^{2(k+1)} - 1 = 2^{2k} \cdot 3 + (2^{2k} - 1) = 3(2^{2k} + r)22(k+1)−1=22k⋅3+(22k−1)=3(22k+r) The step uses 22k+2=22k⋅4=22k(3+1)2^{2k+2} = 2^{2k} \cdot 4 = 2^{2k}(3 + 1)22k+2=22k⋅4=22k(3+1) , and 22k+r2^{2k} + r22k+r is an integer.Example: k=1k = 1k=1 : 24−1=15=4⋅3+3=3⋅52^4 - 1 = 15 = 4 \cdot 3 + 3 = 3 \cdot 524−1=15=4⋅3+3=3⋅5 .
[Mathematical Induction II] For which integers n≥0n \ge 0n≥0 is 2n+1<2n2n + 1 < 2^n2n+1<2n ? Where must an induction proof of it start?
For all n≥3n \ge 3n≥3 , so the basis step is P(3)P(3)P(3) : 7<87 < 87<8 . It fails for n=0,1,2n = 0, 1, 2n=0,1,2 : 1<11 < 11<1 , 3<23 < 23<2 and 5<45 < 45<4 are false.
[Mathematical Induction II] Claim: 2n+1<2n2n + 1 < 2^n2n+1<2n for all integers n≥3n \ge 3n≥3 . Inductive hypothesis: 2k+1<2k2k + 1 < 2^k2k+1<2k for an integer k≥3k \ge 3k≥3 .How does the inductive step show 2(k+1)+1<2k+12(k + 1) + 1 < 2^{k+1}2(k+1)+1<2k+1 ?
2k+3=(2k+1)+2<2k+2k=2k+12k + 3 = (2k + 1) + 2 < 2^k + 2^k = \boldsymbol{2^{k+1}}2k+3=(2k+1)+2<2k+2k=2k+1 , using the inductive hypothesis and 2<2k2 < 2^k2<2k . 2<2k2 < 2^k2<2k holds for all k≥2k \ge 2k≥2 .Example: k=3k = 3k=3 : 2⋅4+1=9<16=242 \cdot 4 + 1 = 9 < 16 = 2^42⋅4+1=9<16=24 .
[Mathematical Induction II] A sequence is defined by a1=2a_1 = 2a1=2 and ak=5ak−1a_k = 5a_{k-1}ak=5ak−1 for all integers k≥2k \ge 2k≥2 . What are a1,…,a4a_1, \dots, a_4a1,…,a4 , and what explicit formula do they satisfy?
2,10,50,2502, 10, 50, 2502,10,50,250 , and an=2⋅5n−1\boldsymbol{a_n = 2 \cdot 5^{n-1}}an=2⋅5n−1 for all n≥1n \ge 1n≥1 . a2=5⋅2a_2 = 5 \cdot 2a2=5⋅2 , a3=5⋅10a_3 = 5 \cdot 10a3=5⋅10 , a4=5⋅50a_4 = 5 \cdot 50a4=5⋅50 .
[Mathematical Induction II] a1=2a_1 = 2a1=2 and ak=5ak−1a_k = 5a_{k-1}ak=5ak−1 for all integers k≥2k \ge 2k≥2 . Claim: an=2⋅5n−1a_n = 2 \cdot 5^{n-1}an=2⋅5n−1 for all integers n≥1n \ge 1n≥1 .How does the inductive step go from ak=2⋅5k−1a_k = 2 \cdot 5^{k-1}ak=2⋅5k−1 to ak+1=2⋅5ka_{k+1} = 2 \cdot 5^kak+1=2⋅5k ?
Apply the recursive definition, then the inductive hypothesis: ak+1=5ak=5⋅(2⋅5k−1)=2⋅5ka_{k+1} = 5a_k = 5 \cdot (2 \cdot 5^{k-1}) = \boldsymbol{2 \cdot 5^k}ak+1=5ak=5⋅(2⋅5k−1)=2⋅5k Basis step: a1=2=2⋅50a_1 = 2 = 2 \cdot 5^0a1=2=2⋅50 .
[Mathematical Induction II] What is a tromino, and what are its two types?
A polyomino made of three attached squares: straight or L-shaped. Solomon Golomb introduced the word polyomino (a generalization of domino) in 1954, as a 22-year-old Harvard student. Polyominoes became the basis of the game Tetris.
[Mathematical Induction II] Theorem (Covering a Board with Trominoes) For any integer n≥1n \ge 1n≥1 , if one square is removed from a 2n×2n2^n \times 2^n2n×2n checkerboard, then … ?
The remaining squares can be completely covered by L-shaped trominoes. Example: a 4×44 \times 44×4 board with one square (black) removed, covered by five L-shaped trominoes.
[Mathematical Induction II] A 2n×2n2^n \times 2^n2n×2n checkerboard with one square removed has 22n−12^{2n} - 122n−1 squares left. Why is that number compatible with a covering by trominoes?
22n−12^{2n} - 122n−1 is divisible by 3, and every tromino covers 3 squares. Example: n=2n = 2n=2 : 16−1=15=5⋅316 - 1 = 15 = 5 \cdot 316−1=15=5⋅3 , so five trominoes.
[Mathematical Induction II] Claim: for every n≥1n \ge 1n≥1 , a 2n×2n2^n \times 2^n2n×2n checkerboard with any one square removed can be covered by L-shaped trominoes.What is the basis step?
A 2×22 \times 22×2 board with one square removed is itself an L, covered by one L-shaped tromino.
[Mathematical Induction II] Claim: for every n≥1n \ge 1n≥1 , a 2n×2n2^n \times 2^n2n×2n checkerboard with any one square removed can be covered by L-shaped trominoes.Inductive step: how is a 2k+1×2k+12^{k+1} \times 2^{k+1}2k+1×2k+1 board with one square removed covered, assuming the claim for 2k×2k2^k \times 2^k2k×2k boards?
Split it into four 2k×2k2^k \times 2^k2k×2k quadrants; one tromino covers the central squares of the three quadrants without the removed square. Now each quadrant is a 2k×2k2^k \times 2^k2k×2k board with one square removed or covered, so the inductive hypothesis covers the rest. The split works because 2k+1=2⋅2k2^{k+1} = 2 \cdot 2^k2k+1=2⋅2k . The removed square (black) is in the top-left quadrant; the tromino (gray) covers one corner square of each of the other three quadrants.
[Strong Induction, Well-Ordering] State the principle of strong mathematical induction for a property P(n)P(n)P(n) and fixed integers a≤ba \le ba≤b .
If P(a),P(a+1),…,P(b)P(a), P(a+1), \dots, P(b)P(a),P(a+1),…,P(b) are true and, for every integer k≥bk \ge bk≥b , the truth of P(a),…,P(k)P(a), \dots, P(k)P(a),…,P(k) implies P(k+1)P(k + 1)P(k+1) , then P(n)P(n)P(n) holds for all n≥an \ge an≥a . The first part is the basis step, the second the inductive step.Example: to prove sn=5n−1s_n = 5^n - 1sn=5n−1 for s0=0s_0 = 0s0=0 , s1=4s_1 = 4s1=4 , sk=6sk−1−5sk−2s_k = 6s_{k-1} - 5s_{k-2}sk=6sk−1−5sk−2 , take a=0a = 0a=0 , b=1b = 1b=1 .
[Strong Induction, Well-Ordering] In a proof by strong mathematical induction, the basis step may require checking P(n)P(n)P(n) for more than one value of nnn .
Example: for a sequence where each term is defined from the two previous terms, the basis step checks the first two terms.
[Strong Induction, Well-Ordering] The basis step of a strong induction proof checked P(n)P(n)P(n) for all integers nnn from aaa through bbb . What does the inductive step suppose, and what does it show?
For any integer k≥bk \ge bk≥b : suppose P(i)P(i)P(i) is true for all integers iii from aaa through kkk , and show that P(k+1)P(k + 1)P(k+1) is true. The supposition is the inductive hypothesis.
[Strong Induction, Well-Ordering] Why can every statement that ordinary mathematical induction proves also be proved by strong mathematical induction?
If P(k)P(k)P(k) alone implies P(k+1)P(k + 1)P(k+1) , then P(a),…,P(k)P(a), \dots, P(k)P(a),…,P(k) together certainly imply P(k+1)P(k + 1)P(k+1) .
[Strong Induction, Well-Ordering] Strong induction: from P(a),…,P(b)P(a), \dots, P(b)P(a),…,P(b) and "for every k≥bk \ge bk≥b , P(a),…,P(k)P(a), \dots, P(k)P(a),…,P(k) imply P(k+1)P(k+1)P(k+1) ", conclude P(n)P(n)P(n) for all n≥an \ge an≥a .How can the same conclusion be reached with ordinary mathematical induction?
Apply ordinary induction to Q(n)Q(n)Q(n) : " P(j)P(j)P(j) is true for all integers jjj with a≤j≤na \le j \le na≤j≤n ", starting at n=bn = bn=b . Q(b)Q(b)Q(b) is the basis step of the strong induction, and Q(k)Q(k)Q(k) implies P(k+1)P(k+1)P(k+1) , so Q(k+1)Q(k+1)Q(k+1) . Hence ordinary and strong induction prove the same statements.
[Strong Induction, Well-Ordering] Strong induction can be stated without a basis step: "for all k≥a−1k \ge a - 1k≥a−1 , if P(i)P(i)P(i) is true for all integers iii from aaa through kkk , then P(k+1)P(k + 1)P(k+1) ". Why does this still give P(a)P(a)P(a) ?
For k=a−1k = a - 1k=a−1 the hypothesis is vacuously true (there is no iii from aaa through a−1a - 1a−1 ), so the implication yields P(a)P(a)P(a) . Writing the basis step anyway is a good habit: the argument for large kkk often fails for small kkk .
[Strong Induction, Well-Ordering] Under which other names is the principle of strong mathematical induction known?
Principle of complete induction, second principle of induction, second principle of finite induction.
[Strong Induction, Well-Ordering] Prove by strong induction that every integer n≥2n \ge 2n≥2 is divisible by a prime number. How does the inductive step treat k+1k + 1k+1 ?
If k+1k + 1k+1 is prime, it divides itself. Otherwise k+1=abk + 1 = abk+1=ab with 2≤a≤k2 \le a \le k2≤a≤k ; a prime ppp divides aaa (inductive hypothesis), so p∣k+1p \mid k + 1p∣k+1 . p∣ap \mid ap∣a and a∣k+1a \mid k + 1a∣k+1 give p∣k+1p \mid k + 1p∣k+1 by transitivity of divisibility. Basis step: 2 is divisible by the prime 2.Example: k+1=15=3⋅5k + 1 = 15 = 3 \cdot 5k+1=15=3⋅5 ; 3∣33 \mid 33∣3 , so 3∣153 \mid 153∣15 .
[Strong Induction, Well-Ordering] Proof that every integer n≥2n \ge 2n≥2 is divisible by a prime: if k+1k + 1k+1 is not prime, write k+1=abk + 1 = abk+1=ab with 1<a,b<k+11 < a, b < k + 11<a,b<k+1 , and use that aaa is divisible by a prime.Why does this proof need strong induction rather than ordinary induction?
The factor aaa can be any integer from 2 through kkk , not necessarily kkk , so the hypothesis must cover all of P(2),…,P(k)P(2), \dots, P(k)P(2),…,P(k) . Example: k+1=21=3⋅7k + 1 = 21 = 3 \cdot 7k+1=21=3⋅7 uses P(3)P(3)P(3) or P(7)P(7)P(7) , not P(20)P(20)P(20) .
[Strong Induction, Well-Ordering] A sequence is defined by s0=0s_0 = 0s0=0 , s1=4s_1 = 4s1=4 and sk=6sk−1−5sk−2s_k = 6s_{k-1} - 5s_{k-2}sk=6sk−1−5sk−2 for all integers k≥2k \ge 2k≥2 . What are s2s_2s2 , s3s_3s3 , and what explicit formula do the terms satisfy?
s2=24s_2 = 24s2=24 , s3=124s_3 = 124s3=124 , and sn=5n−1\boldsymbol{s_n = 5^n - 1}sn=5n−1 for all n≥0n \ge 0n≥0 . s2=6⋅4−5⋅0=24s_2 = 6 \cdot 4 - 5 \cdot 0 = 24s2=6⋅4−5⋅0=24 , s3=6⋅24−5⋅4=144−20=124\ s_3 = 6 \cdot 24 - 5 \cdot 4 = 144 - 20 = 124 s3=6⋅24−5⋅4=144−20=124 .