Help Figuring Out Faulty Proof

Question

In my discrete math class, we're working on faulty proofs. I can't seem to figure out why this proof is faulty. I think it has to due with them assuming $k^2 \le k^2 + 2k$.

Anyone have any ideas?

$\forall n \in \mathbb N_0 : n^2 \le n.$

Proof:
Base Case: When $n = 0,\ 0\le 0, \checkmark$.
Induction hypothesis: Assume that $k^2 \le k$.
Inductive step: Prove $(k + 1)^2 \le k + 1$
We work backwards. $$k^2 \le (k + 1)^2 – 1 \le (k + 1) – 1 = k.$$

Answer 1

How do you justify $(k+1)^2 - 1 \leq (k+1) - 1$?

Answer 2

"Working backwards" in induction proves the statements for all smaller numbers than the base case. You proved $$k^2 \le k \qquad\forall \mathbb N_0 \ni k \color{red} \le 0$$ The latter set is $\{0\}$ so you only proved the base case and the induction step is invalid.

The reason is you actually assumed $(k+1)^2 \le (k+1)$ and proved $k^2 \le k$ from it, so the step was $k+1\to k$ and not $k\to k+1$.

Answer 3

'Working backwards' you proved that $$(k + 1)^2 ≤ k + 1 \implies k^2 ≤ k$$ but you have to prove that $$k^2 ≤ k \implies (k + 1)^2 ≤ k + 1$$