<s>[INST] Proof by Induction: $(1+x)^n \le 1+(2^n-1)x$ I have to prove the following by induction:
$$(1+x)^n \le 1+(2^n-1)x$$
for $n \ge 1$ and $0 \le x \le 1$.
I start by showing that it's true for $n=1$ and assume it is true for one $n$.
$$(1+x)^{n+1} = (1+x)^n(1+x)$$
by assumption:
$$\le (1+(2^n-1)x)(1+x)$$
$$= 1+(2^n-1)x+x+(2^n-1)x^2$$
That is what I was able to do on my own. I do not understand the next step of the solution (they are now using $x$ instead of $x^2$ at the end):
$$Because\,0 \le x \le 1$$
$$(1+x)^{n+1} \le 1 + (2^n-1)x+x+(2^n-1)x$$
$$=1+2(2^n-1)x+x$$
$$=1+(2^{n+1}-1)x$$
Because $0 \le x \le 1$ I assume that $(2^n-1)x^2 < (2^n-1)x$. So in my opinion, I just proved that $(1+x)^{n+1}$ is less than something greater than what I had to prove initially. Why is it enough to prove the original problem?
 [/INST] I'm not exactly clear as to what your final sentence means. But, since $0\le x\le 1$, we know that $x^2\le x\cdot x\le 1\cdot x\le x$, so that
$$(1+x)^{n+1} \le 1 + (2^n-1)x + x + (2^n-1)x^2
    \le 1 + (2^n-1)x + x + (2^n-1)x = 1+2(2^n-1)x + x = 1 + (2^{n+1}-1)x,$$
which is the statement for $n+1$.
</s>