How to write mathematical induction?
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$.
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.
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.