Better proof that $n \leq 2n$ for all natural numbers?

145 Views Asked by At

I tried proving via induction on naturals that $n \leq 2n$ for each natural $n$. Obviously, $0 \leq 2(0)$, and then assuming for any given $n$, $n \leq 2n$, you just show that $n + 1 \leq 2(n + 1).$ (where $n + 1$ is the successor of $n$)

Unfortunately, all I can get is $n + 2 \leq 2(n + 1)$, but from that is seems to follow that $n + 1$ is also $\leq 2(n + 1)$, because $n + 1 \leq n + 2$ if $n \geq 0$, so by transitivity, $n + 1$ is also $\leq 2(n + 1).$

Is there someway to exactly transform $n \leq 2n$ into $n + 1 \leq 2(n + 1)$?

2

There are 2 best solutions below

0
On BEST ANSWER

Using the inductive hypothesis, $\color{blue}{n \leq 2n}$, we know that $$\color{blue}{n}+1\leq \color{blue}{2n} +1 \leq 2n+2 = 2(n+1)$$

0
On

A non-inductive proof.

The usual way to define $a\leq b$ in the natural numbers is to say $a\leq b$ if there is a natural number $c$ such that $a+c=b$.

Now, $n+n=1\cdot n + 1\cdot n = (1+1)n=2n$, so $n\leq 2n$.