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.
Best Answer
I will answer this question with
fourtypical 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$.