Skip to content

8.23 Induction tutorial

  1. Prove that \(\sum_{i=1}^{n}i^{2}=\frac{n(n+1)(2n+1)}{6}\) for all \(n\in\N\)

    Base step: the result is true for n=1 since \(1^2=\frac{1(1+1)(2+1)}{6}\)

    Inductive step: Suppose that the result is true for \(n\), that is \(1^2+2^2+...+n^2=\frac{n(n+1)(2n+1)}{6}\)

    hence \(1^2+2^2+...+n^2+(n+1)^2=\frac{n(n+1)(2n+1)}{6}+(n+1)^2=\frac{n(n+1)(2n+1)+6(n+1)^{2}}{6}=\frac{(n+1)[(n)(2n+1)+6(n+1)]}{6}=\frac{(n+1)(2n^{2}+7n+6)}{6}=\frac{(n+1)([2n+3)(n+2)]}{6}=\frac{(n+1)[(n+1)+1][2(n+1)+1]}{6}\)

    Therefore the result is true for \(n+1\).

    Thus by the induction principle we have that \(\sum_{i=1}^{n}i^{2}=\frac{n(n+1)(2n+1)}{6}\) for all \(n\in\N\)

  2. Use strong induction to show that \(n^2-n-20>0\) for all \(n\geq 6\)​

    Base step

    The result is true for \(n_0=6\) since \(6^2-6-20=10>0\)​

    Induction step

    Suppose that the result is true for \(k\) with \(6\leq k<n\), then we need to show that \(n^2-n-20=(n^2-2n+1)+(n-1)-20=(n-1)^2+(n-1)-20=(n-1)^2-(n-1)-20+2(n-1)\)​

    Since \((n-1)^2-(n-1)-20>0\) and \(2(n-1)>0\)

    We have that \(n^2-n-20>0\) that is the result is true for \(n\).

    Thus by the strong induction principle \(n^2-n-20>0\) for all \(n\geq 6\)

  3. Use induction to show \(n+3<5n^2\) for all \(n\in\N\)

  4. Prove that every subset of \(N_n\) is finite for all \(n\in\N\). (Using induction)

    Base step

    If \(n=1\) then \(\N_1=\{1\}\), then \(A=\emptyset\) or \(A=\N_1\)​

    Inductive step

    Suppose that the result is true for \(n\), that is, every subset of \(N_n\) is finite.

    Let \(A\subseteq \N_{n+1}\), then \(A\setminus \{n+1\}\subseteq \N_n\)​

    Thus \(A\setminus \{n+1\}\) is finite and \(A=(A\setminus\{n+1\})\cup \{n+1\}\) is finite

‍