Prove by induction that $(n - 1)^k \le n^k$

94 Views Asked by At

Let $n,k \in \mathbb N, n \gt 0$.
I was trying to prove by induction that: $$ (n - 1)^k \le n^k $$ (The induction is meant to be on k.)
I started by verifying the inequality in the base cases, which I did by $k = 0$ and $k = 1$, so: $$ (n - 1)^0 = 1 \le 1 = n^0 \\ (n - 1)^1 = n - 1 \le n = n^1 $$

then I have to prove it in the inductive step, so I assume that $(n - 1)^{k} \le n^{k}, \space \forall \space k' < k$: $$ (n - 1)^{k + 1} = (n - 1)^k (n - 1) \le n^k n = n^{k + 1} $$

If I am not wrong, the proof is correct, because in the inductive step I got $(n - 1)^k$ which I assumed to be less or equal than $n^k$ and $(n - 1)$ is less or equal than $n$ by the base case.
So the product of $(n - 1)^k$ and $(n - 1)$ isn't greater than the product $n^k$ and $n$.
Am I right?

1

There are 1 best solutions below

0
On

In the inductive step, we need to prove, $$(n-1)^{k+1} \leq n^{k+1}$$ But we earlier we assumed that $$(n-1)^{k} \leq n^{k}$$ But we can't immediately write $(n-1)^{k+1} \leq n(n-1)$ because we don't know the sign of $(n-1)$

If $n \lt 1$, $$(n-1) \lt 0 \Rightarrow (n-1)^{k+1} \gt n(n-1)$$ which is not the required answer.

If $n \ge 1$, $$(n-1) \ge 0 \Rightarrow (n-1)^{k+1} \leq n(n-1)$$ which gives the correct answer after doing what you have done.

Therefore, your original statement is true $iff$ $n \ge 1$, for $\forall k \in \Bbb{N}$