I'm currently studying Discrete mathematics from a book by Normal L. Biggs and i don't understand the thinking about an example on Strong Principle of Induction,
The example i need help understanding:
Prove that $ n^2 > 7n +1, \forall n \ge 8 $
Solution
The result is true when n=8 because $8^2 =64$ and $ 7 \times 8 = 57 $. Suppose it is true when $ n $ is any number $ k \ge 8 $, that is $ k^2 > 7k + 1 $.
$ (k + 1)^2 = k^2 + 2k + 1 > (7k + 1) + 2k + 1 = 7(k + 1) + 1 + (2k-6) $
Since $ k \ge 8, 2k - 6$ is an natural number and the last expression above is greater then $ 7(k+1) + 1 $. The induction is verified, and so the result is true for all $ n \ge 8 $
And here comes the part i don't understand.
I don't understand, shouldn't it be $ (k+1)^2 > 7(k+1) + 1 $?
Where does the the "$2k$" come from in $ (7k + 1) + 2k + 1 $ and how does it result in the prof? Could someone explain on a basic level on the thinking behind this example?
Alright, so we already have the base case ($k=8$), so we need to prove the inductive hypothesis.
We assume that $$k^2 > 7k +1$$ for some $k\ge8$: we now want to show that $$(k+1)^2 > 7(k+1) + 1.$$ We know that $(k+1)^2 = k^2 + 2k + 1 > (7k+1) + 2k + 1$. We can simplify this last expression to $9k + 2 = 7(k+1) + 1 +(2k - 6)$. As the example remarks, $k\ge8$, so $(2k-6) > 0.$ Thus, $$(k+1)^2 > 7(k+1)+1 +(2k-6) > 7(k+1) + 1 + 0,$$ or more simply, $$(k+1)^2 > 7(k+1) + 1,$$ as was to be shown.
I'll also remark that this example only requires weak induction, since we only need to assume the $k$th holds to prove that the $(k+1)$th case also holds.