6
$\begingroup$

Reading the literature about mathematical induction, I have learnt that there are between 4 and 3 steps in reasoning and writing the proof. I say between 3 and 4 because actually I see that texts and authors of proofs diverge slightly in their explanation and in the style in which the proof is written. This is my impression, at least.

(1) In general, we all agree that the first component is the statement we want to prove and we write it. (2) Then, it follows the base case, when we check the formula for n=1, and we see if the statement holds. So far, there is no difference between proof writers. (3) Afterwards, it follows the assumption, when we write k = n and we state that k is a generic number which appartains to N. Can be whatever natural number. (4) Finally, there is the inductive step, when we write n = k+1, and we proceed with the algebraic manipulation.

I see that some authors concentrate the steps (3) and (4) in an unique step and actually I like it more, as I don't see the need to write one passage exactly the same as the previous one, but with k in place of n! I am asking for your advice as I would like to set once for all my style in writing this kind of proof, grouping steps (3) and (4) in a unique one. However, since that I like to introduce verbally the steps, I am thinking about the right way to introduce the assumption/inductive step. Is it correct the following form, in your opinion? Assume that there exists a general number k+1, with k=n, such that... etc... I am indeed not sure about how to write this sentence, this is why I ask here.

Please, let me know if, where and why I am wrong and also you can point me out if the words I choose are the proper ones - for instance, about "general number". By the way, I am not English mother tongue speaker.

PS. I did not use logical symbols only because I don't know how to edit them but, obviously, I would write the sentence in bold using logical connectives.

$\endgroup$
  • $\begingroup$ maybe should I write: "I assume..." $\endgroup$ – Always learning Oct 26 '15 at 19:27
  • 1
    $\begingroup$ Basic idea of induction: 1. Define the formula $P(x)$, along with the interval on which you are to assume it is true, for example $n\geq m$. 2. Prove the "base case", that is, show that $P(m)$ is true (remember, "m" is the start of the interval from step 1. This is usually a number like 0 or 1). 3. Assuming that $P(m)$ is true for all $m$, show that $P(m+1)$ must be true. $\endgroup$ – galois Oct 26 '15 at 19:40
  • 1
    $\begingroup$ Also try to keep in mind who you're writing the proof for. In my first assignment in university, I was downgraded at some point for not concluding my proof with "by the principle of mathematical induction blah blah". I think they just wanted to make sure people understood what induction was and how it worked, even if I still think it's unnecessarily pedantic. So best check with your tutors etc. what way they want you to write the proof. (This is assuming you are a student.) $\endgroup$ – Fryie Oct 26 '15 at 20:33
  • 1
    $\begingroup$ In general, a proof will be considered correct if it is accepted by its audience (kind of a circular logic here). Who that audience is depends entirely on the context. $\endgroup$ – Fryie Oct 26 '15 at 20:34
  • 1
    $\begingroup$ @jaska: 'Assuming that $P(m)$ is true for all $m$' is simply assuming that the conjecture is true. You can't assume that $P(m)$ is true for all $m$. Instead, we prove that for all $m$ an implication holds: $P(m)\implies P(m+1)$; and then we conclude $P(m)$ is true for all $m \ge 1$. $\endgroup$ – CiaPan Oct 26 '15 at 21:20
9
$\begingroup$

I will answer this question with four typical examples, all different in nature:

Example 1:

Prove by induction that $n^3-n+3$ is divisible by $3$ $\forall \space n \in \mathbb{N^+}$.

For proof by induction; these are the $\color{red}{\mathrm{three}}$ steps to carry out:

Step 1: Basis Case: For $n=1 \implies n^3-n+3= 1^3-1+3=3$ which is divisible by $3$. So statement holds for $n=1$.

Step 2: Inductive Assumption: Assume statement is true for $n=k$ such that $n^3-n+3=\color{blue}{(k^3-k+3)}=\color{blue}{3p} \tag{1}$ Where $p,k \in \mathbb{N^+}$.

Step 3: Prove Statement holds for $n=k+1$ such that $$n^3-n+3=(k+1)^3-(k+1)+3$$ $$=k^3+3k^2+3k+1-k-1+3=3k^2+3k+\color{blue}{(k^3-k+3)}= 3(k^2+k)+\color{blue}{3p}=\color{#180}{3}(k^2+k+p)$$ using our inductive assumption $(1)$ the resulting expression clearly is divisible by $3$.

Hence $n^3-n+3$ is divisible by $3$ $\forall \space n \in \mathbb{N^+}$

QED.

(QED is an abbreviation of the Latin words "Quod Erat Demonstrandum" which loosely translated means "that which was to be demonstrated". It is usually placed at the end of a mathematical proof to indicate that the proof is complete). Alternatively, you can use $\fbox{}$

Example 2:

Use trigonometric identities and induction to prove that

$\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{n} = \left(\begin{array}{cc} \cos (n \theta) & -\sin (n\theta)\\ \sin (n \theta) & \cos (n \theta) \end{array} \right)$

As before, for proof by induction; these are the $\color{red}{\mathrm{three}}$ steps to carry out:

Step 1: Basis Case: For $n=1 \implies$ LHS $=\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{n}$

$=\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{1}$

$=\left(\begin{array}{cc} \cos (1 \theta) & -\sin (1\theta)\\ \sin (1 \theta) & \cos (1 \theta) \end{array} \right)$

$=\left(\begin{array}{cc} \cos (\theta) & -\sin (\theta)\\ \sin ( \theta) & \cos ( \theta) \end{array} \right)=$ RHS. So statement holds for $n=1$.

Step 2: Inductive Assumption: Assume statement is true for $n=k$ such that

$\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{n}$

$=\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{k}$

$=\left(\begin{array}{cc} \cos (k \theta) & -\sin (k\theta)\\ \sin (k \theta) & \cos (k \theta) \end{array} \right)\tag{1}$

Step 3: Prove Statement holds for $n=k+1$ such that

$\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{n}$

$=\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{k+1}$

$=\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{k}$ $\times \left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{1}$

$=\left(\begin{array}{cc} \cos (k \theta) & -\sin (k\theta)\\ \sin (k \theta) & \cos (k \theta) \end{array} \right) \times \left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)$ [using our inductive assumption $(1)$]

$=\left(\begin{array}{cc} \cos\theta\cos (k \theta)-\sin\theta \sin(k\theta) & -\left(\sin \theta\cos (k \theta)+\sin (k \theta)\cos \theta\right)\\ \cos\theta\sin (k \theta)+\sin\theta \cos(k\theta) & \cos\theta\cos (k \theta)-\sin\theta \sin(k\theta) \end{array} \right)$

$=\color{blue}{\left(\begin{array}{cc} \cos (\theta(k+1)) & -\sin (\theta(k+1))\\ \sin (\theta(k+1)) & \cos(\theta(k+1)) \end{array} \right)}$

Where in the last step I used the fact that $$\cos(A \mp B)=\cos A \cos B \pm \sin A \sin B$$ and $$\sin(A \pm B)=\sin A \cos B \pm \cos A \sin B$$ and $\color{blue}{\mathrm{this}}$ is the same result if $n=k+1$ is substituted into the RHS of your original disposition. Hence statement is true for all $n \in \mathbb{N}.$

QED.

Example 3:

Prove by induction that $3^{(3n+4)} + 7^{(2n+1)}$ is divisible by $11$ for all natural numbers $n$:

Step 1: Basis Case: for $n=1$: $P(1)= 3^{(3(1)+4)} + 7^{(2(1)+1)} = 2530$, which is divisible by $11$ so statement holds for $n=1$.

Step 2: Inductive Assumption: Assume statement is true for $n=k$: $P(k) =3^{(3k+4)} + 7^{(2k+1)} = 11a \implies 3^{3k+4} = \color{blue}{11a - 7^{2k+1}}$, where $a \in \mathbb{N}$

Step 3: Prove Statement holds for $n=k+1$:

$P(k+1)= 3^{3k+7} + 7^{2k+3} = 27 \cdot 3^{3k+4} + 49\cdot 7^{2k+1}\tag{1}$

Using the inductive assumption shown in $\color{blue}{\mathrm{blue}}$, $(1)$ becomes:

$27(\color{blue}{11a - 7^{2k+1}})+49\cdot 7^{2k+1}=27\cdot 11a -27\cdot 7^{2k+1}+ 49\cdot 7^{2k+1}=27\cdot 11a +2\cdot 11\cdot 7^{2k+1}=\color{red}{11}(27a+2\cdot 7^{2k+1})$

Hence $3^{3n+4} + 7^{2n+1}$ is a multiple of $\color{red}{11} \space\forall \space n\in \mathbb{N}$

QED.

Example 4:

Prove by induction that $$\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} \quad \forall \space n \in \mathbb{N}$$

Step 1: Basis Case: For $i=1$: $$\sum^{i=k}_{i=1} i^2=\frac{1(1+1)(2\times 1+1)}{6}= \frac{2\times 3}{6}=1$$ So statement holds for $i=1$.

Step 2: Inductive Assumption: Assume statement is true for $i=k$:

$$\sum^{i=k}_{i=1} i^2=\frac{k(k+1)(2k+1)}{6} $$

Step 3: Prove Statement holds for $i=k+1$. You need to prove that for $i=k+1$: $$\sum^{i=k+1}_{i=1} i^2=\color{blue}{\frac{(k+1)(k+2)(2k+3)}{6}}$$

To do this you cannot use: $$\sum^{i=k}_{i=n} i^2=\color{red}{\frac{n(n+1)(2n+1)}{6}} $$ as this is what you are trying to prove.

So what you do instead is notice that: $$\sum^{i=k+1}_{i=1} i^2= \underbrace{\frac{k(k+1)(2k+1)}{6}}_{\text{sum of k terms}} + \underbrace{(k+1)^2}_{\text{(k+1)th term}}$$ $$\sum^{i=k+1}_{i=1} i^2= \frac{k(k+1)(2k+1)}{6}+\frac{6(k+1)^2}{6}$$ $$\sum^{i=k+1}_{i=1} i^2= \frac{(k+1)\left(k(2k+1)+6(k+1)\right)}{6}$$ $$\sum^{i=k+1}_{i=1} i^2= \frac{(k+1)(2k^2+\color{green}{7k}+6)}{6}=\frac{(k+1)(2k^2+\color{green}{4k+3k}+6)}{6}=\frac{(k+1)\left(2k(k+2)+3(k+2)\right)}{6}=\color{blue}{\frac{(k+1)(k+2)(2k+3)}{6}}\quad \forall \space k,n \in \mathbb{N} \quad\fbox{}$$

Which is the relation we set out to prove. So the method is to substitute $i=k+1$ into the formula you are trying to prove and then use the inductive assumption to recover the $\color{blue}{\mathrm{blue}}$ equation at the end.

Observe that in the part marked $\color{green}{\mathrm{green}}$ $7k$ has simply been rewritten as $4k+3k$. From then on you simply take out common factors.

Note that this method is only valid when you have two numbers whose product is $12$ and sum is $7$.

Or, put in another way for the general quadratic $ax^2 +bx +c$, this inspection method is only valid iff you can find two numbers whose product is $ac$ and sum is $b$.

$\endgroup$
  • 1
    $\begingroup$ @Always So the fourth step (if you prefer) is the conclusion, where you state what you have proved and place QED or a Square box at the end to signify the end of the proof. $\endgroup$ – BLAZE Oct 26 '15 at 19:50
  • 1
    $\begingroup$ By the way, it is very elegant the way you write proofs! Compliments! $\endgroup$ – Always learning Oct 26 '15 at 19:56
  • 1
    $\begingroup$ @Always Thanks, that means a lot :) Sorry, had computer problems back then, but the third example is now in place. The idea is the same throughout all three. You always use the Inductive Assumption to complete Step 3. $\endgroup$ – BLAZE Oct 26 '15 at 20:10
4
$\begingroup$

Here is a case that has the step 1 in it...

THEOREM. For $n=1,2,3,\cdots$, $$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2}<2.$$

STEP 1. We will prove by induction: $$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2}\le 2-\frac{1}{n}\tag{1}$$

STEP 2 (base case) Since $1\le 2-\frac{1}{1}$, $(1)$ is true for $n=1$.

STEP 3 (induction hypothesis) Now let $k \ge 1$ and assume that $(1)$ holds for $n=k$. That is: $$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{k^2}<2-\frac{1}{k}$$

STEP 4 (induction step) Now for $n=k+1$: $$ 1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} =1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{k^2}+\frac{1}{(k+1)^2} . $$ By the induction hypothesis, this is $$ \le 2 - \frac{1}{k}+\frac{1}{(k+1)^2} < 2 - \frac{1}{k}+\frac{1}{(k+1)^2}+\frac{1}{k(k+1)} \\ = 2-\frac{1}{k+1} = 2-\frac{1}{n} . $$ Thus, $(1)$ holds for $n=k+1$.

STEP 5 (conclusion) Therefore, by induction, $(1)$ holds for $n=1,2,3,\dots$. From this we get $$ 1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} < 2. $$ as required.

$\endgroup$
2
$\begingroup$

All the examples are great, I dont think I could contribute anything that hasn't been covered. But I thought I might add that, for me, proving the principle of induction via the well ordering principle is what really made it clear to me what was sufficient and correct when proving something via induction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.