Math Induction

Notes and Examples

• Similar to recursion in programming.
• If we have a statement $P(n)$ we show:
  • $P(1)$ is true: Base Case
  • Show that $P(n)⟹P(n+1)$ for every $n\in \mathbb{N}$: Induction Step
  • $P(n)$ is the Induction Hypothesis
• How to prove?:
  • To prove a statement in the form $(\mathrm{\forall }n\in \mathbb{N}),P(n)$
  • Show $P(1)$ is true.
  • Then prove the implication $\mathrm{\forall }n\in \mathbb{N},P(n)⟹P(n+1)$
• • $1+3+5+7+9+11+13=7^2$
  • $1+3+5+7+9+11+13+15=?$
  • $1+3+5+7+9+11+13+15=7^2+15$
  • $1+3+5+7+9+11+13+15=8^2$
  • So we have our case, and if we add 15 to this sequence, then we get the next number ${}^2$.
• • $1+3+5+\cdots +99$
  • $1=1^2$
    • $1+3=1^2+3$
    • $4=2^2$
    • $4+5=2^2+5$
    • $4+5=3^2$
    • $9=3^2$
    • $\dots$
  • For $n\in \mathbb{N}$, let $P(n)$ be $1+3+5+\cdots +(2n-3)+(2n-1)=n^2$
  • Proof
    • $\mathrm{\forall }n\in \mathbb{N}(P(n)⟹(P(n+1)))$
    • Let $n\in \mathbb{N}$.
    • Assume $P(n)$ is true for this $n$.
    • $1+3+5+\cdots +(2n-1)=n^2$
    • Now let's add $P(n+1)$
    • $1+3+5+\cdots +(2n-1)+(2(n+1)-1)$
    • $1+3+5+\cdots +(2n-1)+(2n+2-1)$
    • $1+3+5+\cdots +(2n-1)+(2n+1)$
    • $(1+3+5+\cdots +(2n-1))+(2n+1)$
    • $n^2+(2n+1)$
    • $n^2+2n+1$
    • $\{\begin{array}{l}p=1\\ s=2\\ f=1,1\end{array}$
    • $(n+1)(n+1)$
    • $(n+1{)}^2$
    • So then $P(n+1)$ is true.
• Example 5:
  • $\mathrm{\forall }n\in \mathbb{N},1+2+3+\cdots +n=\frac{n(n+1)}{2}$
  • $P(1)=1$
    • $\frac{1(1+1)}{2}$
    • $\frac{1(2)}{2}$
    • $\frac{2}{2}$
    • $1$
  • We have proven that $P(1)$ is true.
  • Now we want to show that $\mathrm{\forall }n\in \mathbb{N},P(n)⟹P(n+1)$
  • Let $n\in \mathbb{N}$, assume $P(n)$ is true for this $n$.
    • $P(n)=1+2+3+\cdots +n=\frac{n(n+1)}{2}$
      • This is true.
    • $P(n+1)=1+2+3+\cdots +n+(n+1)$
      • This should replace the $n$ in $\frac{n(n+1)}{2}$
    • $P(n+1)=(1+2+3+\cdots +n)+(n+1)$
    • $P(n+1)=\frac{n(n+1)}{2}+(n+1)$
    • $P(n+1)=\frac{n(n+1)}{2}+(n+1)\cdot \frac{2}{2}$
    • $P(n+1)=\frac{n(n+1)}{2}+\frac{2(n+1)}{2}$
    • $P(n+1)=\frac{n(n+1)}{2}+\frac{2(n+1)}{2}$
    • $P(n+1)=\frac{n(n+1)+2(n+1)}{2}$
    • $P(n+1)=\frac{(n+2)(n+1)}{2}$

Practice

• 1

  • Prove that for any $n\in \mathbb{N}$, $n^3+5n$ is divisible by $6$.
  • $P(n)=6\mid n^3+5n$
  • We want to prove that $P(n+1)$ is true.
  • Let's show $P(1)$ is true:
    • $6\mid (1{)}^3+5(1)$
    • $6\mid 6$
    • This is true because $6=6a$ for some $a\in \mathbb{Z}$. Clearly $a=1$
  • Let's prove that $\mathrm{\forall }n\in \mathbb{N},P(n)⟹P(n+1)$:
    • Let's assume $P(n)$ is true for the current $n$.
    • $P(n+1)=6\mid (n+1{)}^3+5(n+1)$
    • $P(n+1)=6\mid (n+1)(n+1)(n+1)+5n+5$
    • $P(n+1)=6\mid (n^2+2n+1)(n+1)+5n+5$
    • $P(n+1)=6\mid (n^3+n^2+2n^2+2n+1)+5n+5$
    • $P(n+1)=6\mid (n^3+3n^2+2n+1)+5n+5$
    • $P(n+1)=6\mid n^3+3n^2+2n+1+5n+5$
    • $P(n+1)=6\mid n^3+3n^2+7n+6$
    • $P(n+1)=6\mid n^3+3n^2+2n+5n+6$
    • $P(n+1)=6\mid (n^3+5n)+3n^2+2n+6$
    • Incorrect algebra above, the following is true
    • $P(n+1)=6\mid (n^3+5n)+3(n^2+n+2)$
    • By induction we know the first term is divisible by $6$.
    • So $6\mid n^3+5n$ but does $6\mid 3(n^2+n+2)$?
    • $n^3+5n=6a$ for some $a\in \mathbb{Z}$.
    • $6\mid 3(n^2+n+2)$ so then:
      • $3(n^2+n+2)=6m_2$ for some $m_2\in \mathbb{Z}$.
      • So we know that $n^2+n+2$ should be even, if we multiply any even by $3$, we get something divisible by $6$.
        • Proof:
          • Case 1: even
            • Let $n=2a$
            • $(2a{)}^2+2a+2$
            • $4a^2+2a+2$
            • $2(2a^2+a+1)$
            • Since we can factor out $2$, this is even.
          • Case 2: odd
            • $n=2a+1$
            • $(2a+1{)}^2+(2a+1)+2$
            • $(2a+1)(2a+1)+2a+1+2$
            • $(2a+1)(2a+1)+2a+3$
            • $(4a^2+4a+1)+2a+3$
            • $4a^2+4a+1+2a+3$
            • $4a^2+6a+4$
            • $2(2a^2+3a+2)$
            • I can factor out $2$, so it's always even no matter what.
      • So let $n^2+n+2=2m_1$ for some $m_1\in \mathbb{Z}$
      • So we have $(n+1{)}^3+5(n+1)=n^3+5n+3(n^2+n+2)$
      • $(n+1{)}^3+5(n+1)=6m_2+3(2m_1)$
      • $(n+1{)}^3+5(n+1)=6m_2+6m_1$
      • $(n+1{)}^3+5(n+1)=6(m_1+m_2)$ which is divisible by $6$ so the whole thing is.

• 2

  • Prove that for any $n\in \mathbb{N}$, $1\cdot 2+2\cdot 3+3\cdot 4+\cdots +n(n+1)=\frac{n(n+1)(n+2)}{3}$
  • $P(n)=1\cdot 2+2\cdot 3+3\cdot 4+\cdots +n(n+1)=\frac{n(n+1)(n+2)}{3}$
  • Prove the base case:
    • $P(1)=1\cdot 2=\frac{1(1+1)(1+2)}{3}$
    • $P(1)=1\cdot 2=\frac{1(2)(3)}{3}$
    • $P(1)=1\cdot 2=\frac{6}{3}$
    • $P(1)=1\cdot 2=2$
    • Base case proven
  • Prove that $\mathrm{\forall }n\in \mathbb{N},P(n)⟹P(n+1)$
    • $P(n+1)=1\cdot 2+2\cdot 3+\cdots +n(n+1)+(n+1)(n+2)$
    • $P(n+1)=(1\cdot 2+2\cdot 3+\cdots +n(n+1))+(n+1)(n+2)$
    • $P(n+1)=\frac{n(n+1)(n+2)}{3}+(n+1)(n+2)$
    • $P(n+1)=\frac{n(n+1)(n+2)}{3}+((n+1)(n+2))\frac{3}{3}$
    • $P(n+1)=\frac{n(n+1)(n+2)}{3}+\frac{3(n+1)(n+2)}{3}$
    • $P(n+1)=\frac{n(n+1)(n+2)+3(n+1)(n+2)}{3}$
    • $P(n+1)=\frac{n(n^2+3n+2)+3(n^2+3n+2)}{3}$
    • $P(n+1)=\frac{n^3+3n^2+2n+3n^2+9n+6}{3}$
    • $P(n+1)=\frac{n^3+6n^2+11n+6}{3}$
    • Need to turn this into $\frac{(n+1)((n+1)+1)((n+1)+2)}{3}$
    • Need to turn this into $\frac{(n+1)(n+2)(n+3)}{3}$
    • $P(n+1)=\frac{n^3+6n^2+11n+6}{3}$
    • Using the thing from high-school we can check roots by shoving shit into it.
    • $P(n+1)=\frac{n^3+6n^2+11n+6}{3}$
    • $n=-1,-2,-3$
      • $\{\begin{array}{l}n=-1,-2,-3\\ n+1=0\\ n+2=0\\ n+3=0\end{array}$
    • $P(n+1)=\frac{n^3+6n^2+11n+6}{3}$
    • $P(n+1)=\frac{(n+1)(n+2)(n+3)}{3}$
    • So this has been proven