Induction Proof Verification via Binomial Theorem

Question

I am studying from a text with an overview of discrete mathematics in the beginning. The problem in question is to prove by induction that

$(1+x)^{k+1}$ $\geq$ $1+nx$ for all naturals, where $x > 1$

I proved this by induction in a similar vein as the solution in the back of the book. The following 'proof' in this post was my first attempt, but I was unsure about its validity. Specifically in the induction step (proving that $n+1$ is true) I am afraid that I am making the assumption that it is true before showing that it is true.

Proof

As a base case, take $n=1$. In this case the inequality holds. Now suppose this is true up to the $k$th natural number. We will now show that this is true for $k+1$.

$(1+x)^{k+1}$ $\geq$ $(1+(1+k)x)$

By the binomial theorem the left and right side give

$x^{0}$ + ${k+1\choose 1}x$ + ... + $x^{k+1}$ $\geq$ $1+x(k+1)$.

After evaluating the left hand side we obtain

$1$ + $(k+1)x$ + ... + $x^{k+1}$ $\geq$ $1+(k+1)x$ .

Subtract the right hand side from the first two terms on the left and we have

${k+1\choose 2}x^{2}$ + ... + $x^{k+1}$ $\geq$ $0$ .

Because the left hand side is the sum of positive terms* it is certainly greater than or equal to zero.

QED

*I suppose this is only true if for $x>-1$ where $x$ is a natural. Should x be a negative real number less than zero but greater than negative one this would not hold. Thoughts?

An evaluation of whether or not this is otherwise a valid proof by induction would be greatly appreciated. I'd be grateful to hear any other criticisms of my mathematical writing in general.

Edit: thanks to all who proved this in the comments. I actually did it that way as well. The real reason for the post was because I knew I was making a logical error in how I tried to prove via the binomial theorem.

Answer 1

The statement should be

• $(1+x)^{k}\geq 1+kx$ for all naturals, where $x > 1$

this is the Bernoulli inequality and it is valid for any $x\ge-1$ (in the link you may find all the information about other cases).

No your proof is not to by induction since to prove you are not using any induction hypothesis but another result (the binomial theorem).

Answer 2

By using the principle of induction you want to show somehow that the case $n=k+1$ follows the correctness of the case $n=k$. So you need to use the hypotesis somewhere. In this case the induction hypotesis would be

$$(1+x)^k~\geq~1+kx$$

And like you mentioned this holds for $n=1$. Now just start with this and multiply both sides by $(1+x)$ and continue as it follows

$$\begin{align} (1+x)^k~&\geq~1+kx\\ (1+x)^k(1+x)~&\geq~(1+kx)(1+x)\\ (1+x)^{k+1}~&\geq~1+kx+x+kx^2\\ (1+x)^{k+1}~&\geq~1+(k+1)x+kx^2\\ \end{align}$$

Now we only to take care of the extra term $kx^2$. By assuming that $k>0$, which is true by the fact that we are using the mathematical induction where we are only dealing with $k\in\mathbb{N}$, we can use the inequality

$$a^2~>~0~~\text{and so}~~k\cdot x^2~>~k\cdot 0~,~kx^2~>~0$$

which holds for any number except $0$. So we can proceed by

$$\begin{align} 1+(k+1)x+kx^2~&\geq~1+(k+1)x \end{align}$$

which leads to

$$\begin{align} (1+x)^{k+1}~\geq~1+(k+1)x+kx^2~\geq~1+(k+1)x \end{align}$$

and by the transitivity of inequalities we arrive at

$$(1+x)^{k+1}~\geq~1+(k+1)x$$

The advantage of this proof that you are only forced to use one other inequality, the one about the square of a number, and not something more complicated like the Binomial Theorem.

Answer 3

As mentioned above, you do not use your induction hypothesis, so you are not really doing a proof by induction. However, there is a more serious (although very common) problem with the way you have structured your proof. Your concern about assuming the claim you are trying to prove is spot on. In your very first line of math you start with what it is you are trying to show and work from there toward something you know to be true in the last line, but this is not in general a valid form of reasoning.

If the statement you start out with is false, you may (through a series of algebraic manipulations) arrive at a true statement, so you cannot use this method to determine whether the statement you started with was true. Take this as a simple example: $-1 = 1\implies(-1)^2 = 1^2\implies1=1$. The fact that the last line is true does not allow me to conclude that the first line was true (it's obviously not!). If all of your steps are "reversible" (unlike squaring) you can do this, but it is still best practice to avoid arguing this way in all circumstances. In general, you want to start from one side of what you want to prove and work toward the other (in a proof by induction, this is where you will need to use the inductive hypothesis.

E.g. in this problem: Suppose the $(1+x)^k \geq 1+kx$ for $x>1$ for some natural number $k$. Consider $(1+x)^{k+1}$. By rules of exponents, we can write $(1+x)^{k+1} = (1+x)(1+x)^k$. By the induction hypothesis, we know that $(1+x)^k \geq 1+kx$, and since $(1+x)$ is positive for $x>1$, we can say $(1+x)(1+x)^k \geq (1+x)(1+kx)$.

I'll let you take it from there!

Answer 4

You needn't invoke the Binomial theorem, and your proof is not inductive.

The induction hypothesis is

$$(1+x)^n\ge 1+nx$$

and you need to show that this implies

$$(1+x)^{n+1}\ge 1+(n+1)x.$$

Indeed,

$$(1+x)^{n+1}=(1+x)^n(1+x)\ge^1 (1+nx)(1+x)\ge^2 1+x+nx=1+(n+1)x.$$

$^1$ by the induction hypothesis. $^2$ because we drop the term $x^2$.

As the statement is true for $n=1$, it is true for all $n$.