Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was struggling to get my head around proof by induction for inequalities when I came across a method described at The Math Forum (first answer). Here Dr. Ian goes ahead and compares the changes in the inequalities made by substitution ($n=k+1$), by assuming the original inequality to be equal.

In the original example $$ \begin{align} \text{For }n=k&\quad (1+x)^k \geq (1+kx)\\ \text{For }n=k+1&\quad (1+x)^k\underbrace{(1+x)}_{\text{change}}\geq(1+kx)\underbrace{+\,x}_{\text{change}} \end{align} $$ Now Dr. Ian claims that

there are two things left to do. The first is to show that (or explain the conditions under which) something multiplied by (1+x) is greater than the same thing plus x: $$ \alpha * (1+x) >= \alpha + x $$

I have found this method very appealing as it significantly simplifies the algebra - instead of expanding one side and forming a conjucture as to why it will be larger than the other, I only need to isolate $\alpha$ and show that it holds true when substituted back into the original inequality.

However my only concern is the assumption that $\alpha=(1+x)^k=(1+kx)$, since they are in fact not equal, but greater or equal. Is it fair to make this assumption nonetheless, making this method a valid strategy for proving inequalities by induction?

share|improve this question
2  
He uses poor style in other ways, writing down and manipulating the inequality he wants to prove. Very high school. And students confuse inequalities with equations, anything that encourages that is not a good thing. –  André Nicolas Apr 3 '12 at 13:58

1 Answer 1

up vote 3 down vote accepted
+50

The method is a special case of multiplicative telescopy. This works as follows. To prove that $\rm\:g(n) \ge h(n)\:$ for all $\rm\:n\in \mathbb N\:$ it suffices to prove $\rm\:f(n) = g(n)/h(n) \ge 1\:$ for all $\rm\:n\in N,\:$ presuming $\rm\:h(n)\ne 0$. Now consider an inductive proof that $\rm\:f(n) \ge 1.\:$ Suppose we've proved the base case $\rm\:f(0)\ge 1.\:$ The inductive step $\rm\:f(k)\ge 1\:$ $\Rightarrow$ $\rm\:f(k+1)\ge 1\:$ will follow if the "incremental change" = successive term ratio from $\rm\:f(k)\:$ to $\rm\:f(k+1)\:$ is $\ge 1,\:$ i.e.

$$\rm f(k)\ge 1,\ \dfrac{f(k+1)}{f(k)} \ge 1\ \ \Rightarrow\ \ f(k+1)\: =\: f(k)\:\dfrac{f(k+1)}{f(k)} \ge 1$$

Thus the proof by induction succeeds if we can prove that $\rm\:f(k+1)/f(k) \ge 1\:.$ In your example this is $\rm\:(1+x)\:(1+kx)/(1+kx+x) \ge 1\:$, the same inequality considered by Dr. Ian. However, viewing it from the telescopy perspective lends further insight. Namely, it allows us to view the induction as the special case of the trivial induction that a product of terms $\ge 1$ is $\ge 1,\:$ since by telescopy any sequence $\rm\:f(n)\:$ is the product of its term ratios, viz.

$$\rm f(0)\ \ \prod_{k\:=\:0}^{n-1}\ \frac{f(k+1)}{f(k)}\ \ = \ \ \ \color{red}{\rlap{--}f(0)}\frac{\color{green}{\rlap{--}f(1)}}{\color{red}{\rlap{--}f(0)}}\frac{\color{royalblue}{\rlap{--}f(2)}}{\color{green}{\rlap{--}f(1)}}\frac{\phantom{\rlap{--}f(3)}}{\color{royalblue}{\rlap{--}f(2)}}\ \ \cdots\ \ \frac{\color{brown}{\rlap{--}f(n-1)}}{\phantom{\rlap{--}f(n-2)}}\frac{f(n)}{\color{brown}{\rlap{----}f(n-1)}}\ =\ \ f(n) $$

So once we've proved that $\rm\:f(0)\ge 1$ and $\rm\:f(k+1)/f(k)\ge 1\:$ it follows from the above product representation of $\rm\:f(n)\:$ that $\rm\:f(n)\ge 1\:$ by invoking the Lemma that a product of reals $\ge 1$ is $\ge 1$. Note that the inductive proof of this Lemma is much more obvious than the inductive proof of the original inequality - so obvious that it is trivial. Similarly, one may use telescopy to reduce many inductive proofs to simpler (obvious) normal forms, e.g. $\rm\:1^n = 1.\:$ See my posts on telescopy for many further examples.

share|improve this answer
2  
+1, excellent answer. In none of my books, nor searching the internet have I found any mention of multiplicative telescopy, that you speak of, even though it is (implicitly) used in worked examples. So, to summarize, Dr. Ian's method is completely fine and is a valid method for mathematical induction? –  Milosz Wielondek Apr 3 '12 at 16:51
    
Also, how did you get $\rm\:f(k+1)/f(k) \ge 1$ to be $\rm\:(1+x)\:(1+kx)/(1+kx+x) \ge 1$? Moreover, it does not appear to be the same inequality considered by Dr. Ian - am I missing something here? –  Milosz Wielondek Apr 3 '12 at 18:07
    
@Milosz $\rm\ f(k)\: =\: \dfrac{(1+x)^k}{1+kx}\ \Rightarrow\ \dfrac{f(k+1)}{f(k)}\: =\: \dfrac{(1+x)^{k+1}}{(1+x)^{k{\phantom{ +1}}}}\:\dfrac{(1+kx)}{(1+kx+x)}\ =\ \dfrac{(1+x)(1+kx)}{1+kx+x}\qquad$ So $\rm\:f(k+1)/f(k)\ge 1^{\!\!\!\!\!\!\!\!\!\!\phantom{M^M}}\iff (1+x)\:(1+kx)\ge 1+kx+x,\:$ i.e. $\rm\:(1+x)\:\alpha \ge \alpha + x\:$ for $\rm\:\alpha = 1+kx,\:$ which is precisely the inequality considered by Dr. Ian. –  Bill Dubuque Apr 3 '12 at 18:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.