6
$\begingroup$

Please help. I've been stuck on this for 2 days. Haven't found any easy explaining text.

The question is:

Prove by mathematical induction that :

$$ \sum_{r=1}^n r3^r = \frac{3}{4} \left[ 3^n \left( 2n-1\right)+1 \right] $$

I've done a lot of stuff but can't put them down in tex properly.

  • 1
    The following two question are very similar to this one: [Proving $\sum\limits_{i=0}^n i 2^{i-1} = (n+1) 2^n - 1$ by induction](http://math.stackexchange.com/questions/87030/proving-sum-limits-i-0n-i-2i-1-n1-2n-1-by-induction) and [How to compute the formula $\sum \limits_{r=1}^d r \cdot 2^r$?](http://math.stackexchange.com/questions/11464/how-to-compute-the-formula-sum-limits-r-1d-r-cdot-2r)2012-04-22

5 Answers 5

23

When tackling exercises of this sort the important thing is to remember to use the induction hypothesis correctly.

In proving summation formulas it is often the case that we need to replace the first $n$ terms in the proof of $n+1$ by the formula given to us by the induction hypothesis. The rest is mostly algebraic manipulations. In this case, a proof would go as follows:

Induction base: $n=1$, we have that $1\cdot3^1=3=\dfrac34[3(2\cdot1-1)+1]=\dfrac34\cdot4=3$.

Induction step: Suppose that the sum formula holds for $n$, let us prove it for $n+1$:

$$\begin{align} \sum_{r=1}^{n+1}r3^r =\\ &=\sum_{r=1}^nr3^r+(n+1)3^{n+1} &\text{we take out the last summand from the }\sum\\ &=\frac34[3^n(2n-1)+1]+(n+1)3^{n+1} &\text{now we use the induction hypothesis for }n\\ &=\frac{3^{n+1}(2n-1)+3+4(n+1)3^{n+1}}4 &\text{common denominator}\\ &=\frac{3^{n+1}(2n-1+4n+4)+3}4 &\text{gathering the }3^{n+1}\\ &=\frac{3^{n+1}(6n+3)+3}4 &\text{summation inside the parenthesis}\\ &=\frac{3^{n+2}(2n+1)+3}4 &\text{taking a common divisor from }6n+3\\ &=\frac34[3^{n+1}(2n+1-1+1)+1] &\text{taking out }\frac34\text{ and writing }+1-1\\ &=\frac34[3^{n+1}(2n+2-1)+1] &\text{summation}\\ &=\frac34[3^{n+1}(2(n+1)-1)+1] &\text{Q.E.D} \end{align}$$

  • 3
    -1 For complete lack of pedagogical value. Where did the inductive idea come from? Is there some general idea here or is it completely ad-hoc? Mathematics should not be pulled out of a hat like magic.2012-04-21
  • 3
    @Bill: Are you downvoting me for the sole reason that I dared comment on your second answer? I find it hard to believe that you will only downvote an answer for lack of insight, if you would - you would have to use all your reputation for downvoting.2012-04-21
  • 0
    I explained at length my reason for the downvote (unlike the person who downvoted my answer). If you improve the answer to address the issues I raised then I will be happy to remove the downvote.2012-04-21
  • 9
    @Bill: I explained my downvote to your answer in my comment to Vadim. It is simply **wrong** to answer "*First prove this general theorem by induction...*" to a question which essentially says "I got stuck on this induction".2012-04-21
  • 0
    I have much experience teaching these topics, having taught induction to thousands of students for decades.2012-04-21
  • 3
    @Bill: I have taught induction to hundreds in the past two years. I am fairly confident in my ability to choose my answers.2012-04-21
  • 0
    In addition I know algorithms for summation (definite and indefinite), having invented some of them while working with Gosper et. al. Perhaps after learning such your viewpoint would not be so different from mine. Till then we'll simply have to agree to disagree.2012-04-21
  • 0
    @Bill: Until then. I'll drink to that (avoid whisky with cola, it's not as good as they say it is!)2012-04-21
  • 0
    Thank you. I have another question for you!2012-04-21
  • 0
    @Mob: Which is?2012-04-21
  • 0
    @Asaf I added an introduction to my answer. Perhaps this will help you to better understand my viewpoint.2012-04-21
  • 0
    @AsafKaragila $$ \sum_{r=1}^n \frac{1}{r(r+1)} = \frac{n}{n+1} $$2012-04-21
  • 2
    @Mob: This is something to be asked in a new question altogether. Before doing that I suggest you try tackling it slowly and step by step. I will give you the following hint: $(n+1)^2=n^2+2n+1$ is a very useful factorization.2012-04-21
  • 0
    Ok. I would tackle this myself. Hope you would be available if I run into problems.2012-04-21
  • 0
    I'm stuck. . . . . Sir2012-04-21
  • 0
    Stuck at 2/n(n+2)2012-04-21
  • 3
    @Mob What if $\frac{1}{r(r+1)}$ is just $\frac{1}{r}-\frac{1}{1+r}$?2012-04-22
17

Introduction $\ $ To address some comments below, it is worth adding some introductory remarks. Generally, devising inductive proofs is a difficult endeavor, possibly requiring real ingenuity, such as elucidating hidden innate structure, or devising an effective strengthening of the induction hypothesis, etc. While generally there is no universal method for accomplishing this, there are various widely applicable classes of inductive methods that have been abstracted out of common inductive proofs and encapsulated into conveniently reusable form. Perhaps the simplest and most ubiquitous is the method of telescopy, which conveniently abstracts inductive proofs involving cancelling neighboring terms in sums and products.

If you follow the hint given below, you will discover a simple one-line inductive proof of said Fundamental Theorem. Once you have this theorem available, all similar inductions of this telescopic type become completely trivial: they reduce to simply checking equality of polynomials (which, unlike devising inductive proofs, requires no ingenuity whatsoever). If you master these simple ideas then you will be able to easily tackle many of the induction exercises in your textbooks. Further, you will gain some experience with learning how to abstract out the inductive essence of the matter - which is key when one meets new more complex types of inductions.

If you continue your mathematical studies you will discover other methods of induction that have been conveniently encapsulated for reuse (e.g. maximality principles such as Zorn's Lemma). Strangely, however, one rarely finds any discussion of telescopic induction in textbooks. I learned / discovered these methods only because I was lucky enough to have been exposed to a very stimulating environment as a student, e.g. working with the modern-day Ramanujan Bill Gosper, while constructing effective algorithms for summation (and integration) for Macsyma, and learning from the masters while browsing the open stacks of the MIT Libraries (encouraged by references from walking encyclopedias like Rota). Once one knows the algorithms, it is only natural for one interested in teaching to ponder whether any of the algorithmic theory can be useful pedagogically.

The methods expounded in my many posts on induction attempt to convey some simpler instances of said general algorithms. These posts may require slightly more effort to comprehend than other posts employing ad-hoc techniques. But the reward for this little extra effort is tremendous. Never again for these types of inductions will you find yourself wandering aimlessly in search of the key idea needed to achieve an induction. This is analogous to attempting to computing areas under curves without knowing calculus (as did the ancients such as Archimedes, with much inegenuity) vs. the mechanical calculation of such areas by applying formulas for integration. Theory almost always conquers ad-hoc methods. Further, when, as here, the theory (telescopy) is short and elementary, there is no compelling reason to limit oneself to ad-hoc methods. Hence:

Hint $\: $ First trivially inductively prove the Fundamental Theorem of Difference Calculus

$$\rm\ F(n)\ =\ \sum_{i\: =\: 1}^n\:\ f(i)\ \ \iff\ \ \ F(1)=f(1),\,\ \ F(n) - F(n\!-\!1)\ =\ f(n)\ \ {\rm for}\ \ n> 1$$

Your special case $\rm\:f(i) = i\:\!3^n\:$ now follows immediately by applying $(\Leftarrow)$ above by noting

$$\rm\ F(n) =\ \frac{3}{4} \left( 3^n (2n-1)+1\right) \ \Rightarrow \ F(1) = 3= f(1),\ \ F(n)-F(n\!-\!1) = n\:\!3^n = f(n) $$ Note that by encapsulating the induction in the general Fundamental Theorem we have eliminated any need for induction ingenuity, so reducing the proof to a mechanical algebraic calculation, viz. checking that $\rm\:F(n)-F(n-1) = f(n).$

The inductive proof of the Fundamental Theorem is much more obvious than that for your special case because the telescopic cancellation is obvious at this level of generality, whereas it is usually obfuscated in most specific instances (often greatly so). Namely, the proof of the Fundamental Theorem is just a rigorous inductive proof of the following telescopic cancellation

$$\rm \underbrace{\overbrace{\color{#c00}{F(1)}}^{\large \color{#c00}{f(1)}}\phantom{-\color{#c00}{F(1)}}}_{\large =\ 0}\!\!\!\!\!\!\!\!\!\!\!\!\!\overbrace{-\,F(1)\!+\!\phantom{F(2)}}^{\large f(2)}\!\!\!\!\!\!\!\!\! \underbrace{F(2) -F(2)}_{\large =\ 0}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\overbrace{\phantom{-F(2)}+ F(3)}^{\large f(3)}\!\!\!\!\!\!\!\!\!\!\underbrace{\phantom{F(3)}-F(3)}_{\large =\ 0}+\,\underbrace{\cdot\ \cdot\ }_{\large =\,0\,}\overbrace{\cdot\ +F(n)}^{\large f(n)}\ =\ F(n) $$

The inductive step amounts to doing the next step of the above telescopic cancellation, by adding $\rm\,f(n\!+\!1) = -F(n) + F(n\!+\!1)\,$ to the above, which adds $\rm\,f(n\!+\!1)$ to the LHS sum $\rm\,f(1)+\cdots f(n),\,$ and adds $\rm\ -F(n)+F(n\!+\!1)$ to the RHS $\rm\,F(n),\,$ yielding $\rm\,F(n\!+\!1),\,$ resulting in the $\rm\,n\!+\!1\,$ case of the displayed equation. Stripped of intuitive motivation and slightly rearranged the proof is:

The $\rm\,n=1\,$ base case $\rm\,\color{#c00}{F(1) = f(1)}\,$ is true by hypothesis, and the inductive step is obvious

$$\begin{align}\rm F(n\!+\!1)\ &=\rm\ \ \color{#0a0}{F(n)}\ \ +\, f(n\!+\!1)\ \ \ {\rm by\ hypothesis}\\ &=\rm \color{#0a0}{\sum_{i=1}^n f(i)} + f(n\!+\!1)\ \ \ {\rm by\ }\color{#0a0}{\rm induction}\\ &=\rm \sum_{i=1}^{n+1} f(i) \end{align}$$

That proves the nontrivial direction $(\Leftarrow)$ of the Theorem (the reverse direction is clear).

For further discussion see my many posts on telescopy, some of which give examples where Theorem is more naturally viewed as a uniqueness theorem for (first order) recurrences.

  • 3
    While I agree that proving the general fact is not much harder than proving this particular case, I cannot see how a beginner will find this an easier approach.2012-04-21
  • 3
    @AsafKaragila: Not every answer must adress the OP. I find it useful to learn about different approaches to the same problem, and the OP has plenty of elementary answers at his disposal.2012-04-21
  • 0
    @Fernando: I agree, of course. However this might fit a generalized question. Not this question. I think that someone that can understand *this* answer could have seen this from the previous answer Bill gave on this thread.2012-04-21
  • 1
    @Asaf I prefer to teach a student how to fish vs. serving them one fish on a platter.2012-04-21
  • 2
    I think there are plenty of other direct approaches to the problem. I always appreciate when people try to generalize solution as much as possible keeping it at the same time straightforward and simple, because this is what the whole math is about. Definitely, Mob can learn something from this answer.2012-04-21
  • 0
    @Asaf I think your critique is more appropriate for the other Bill's answer, using the derivative. While the technique is definitely useful, this question is a wrong place to put it, cause it has nothing to do with the induction, which was explicitly asked for in the OP. Moreover, it requires some more advanced facts about the series to be proved first, and without explicit mentioning of the facts, it might appear to the learner that you can always do the same thing.2012-04-21
  • 7
    @Vadim: When you write a question "I have a problem with a basic induction problem" the answer **cannot** be "First prove this theorem by induction, then use it like this...". This is the heart of my problem with this answer.2012-04-21
  • 0
    @Downvoter If there is something that is not clear then please feel free to ask questions and I will happily elaborate. **Such telescopy is the master method for tackling induction problems of this type** so it is essential to understand this.2012-04-21
  • 0
    @Asaf I see. Anyway, I do not see any reason for downvoting your or Bill's answer. Yours is the exact thing the OP asked for, explained step-by-step (even with just too many steps :) ), Bill's is some kind of generalization aimed to teach the technique which is definitely helpful and appropriate as an answer as well.2012-04-21
  • 5
    Please I am a student. Trying to learn the basics. This is way too advanced for me.2012-04-21
  • 2
    @Mob Why do you think that it is too advanced? I have taught telescopy to bright elementary school students. If you tell me what is not clear then I will explain further. The method I explained is a *much* simpler way to discover the proof than is any other ad-hoc way.2012-04-21
  • 0
    @Bill: I retracted my downvote (and discovered a minor bug while at it), I have one qualm though - ad hoc tricks are sometimes very useful to remember later on. Teaching from the very beginning a "magic method" is great but it also takes away the long road students learn how to improvise and do things "by hand".2012-04-21
  • 1
    Bill, I have seen you link to your "many posts on telescopy" many times and can't help but wonder: would you be interested in creating an "Overview of Induction" resource along the lines of what is discussed in [this meta thread](http://meta.math.stackexchange.com/q/3967/7850)? Of course, any such Overview of Induction (consisting of MSE answers) would probably be mostly your work anyway... Just a thought!2012-04-22
  • 2
    Telescopy is a great idea. It seems to be a great way to show students the power of abstraction.2012-04-22
2

Suppose $\sum_{r=1}^n r3^r = \frac 34 (3^n(2n-1)+1)$ holds for $n= N$.

Then $\sum_{r=1}^{N+1} r3^r = \sum_{r=1}^{N} r3^r + (N+1)3^{N+1} = \frac 34 (3^N(2N-1)+1)+ (N+1)3^{N+1}$.

You just have to check the equality holds for $n=1$.

  • 0
    Thanks but I don't understand. Please I'm trying to learn.2012-04-21
  • 0
    @Mob: What is it that you don't understand?2012-04-21
  • 0
    The method Fernando used is called strong induction. Similar but different to the mathematical induction you are used to. Google or wikipedia it2012-04-21
  • 0
    This is advanced. I'm looking for the normal method, with explanations if possible.2012-04-21
  • 0
    Well, in short, let me explain what it is. You show the basis case P(1) is true. Then you assume P(n) is true for all n =< N, and try to show that P(n+1) is true. In "normal" mathematical induction, remember you only assume P(n) is true. Can you see how strong mathematical induction works? (Hint: it is obvious lol)2012-04-21
  • 1
    Strong induction is not neccessary (i.e. "holds for all $n \leq N$" can be replaced by "holds for $n=N$")2012-04-21
  • 0
    Yes but it is useful here for a shorter proof I think.2012-04-21
  • 0
    @sdcvvc: Indeed. Maybe using strong induction was a bit overkill.2012-04-21
  • 0
    @Adam: It does not shorten the proof.2012-04-21
  • 0
    I don't think your proof actually requires strong induction. Or am I missing something?2012-04-21
  • 0
    @DavidMitra: It doesn't. I'll edit it.2012-04-21
  • 0
    You're right, it doesn't shorten the proof. My bad. It's good to know what strong induction is though...2012-04-21
2

when $n=1$, true, Suppose when $n=k$ true, i.e., $\sum_{r=1}^k r3^r = \frac{3}{4} \left[ 3^k \left( 2k-1\right)+1 \right]$. Then $\sum_{r=1}^{k+1} r3^r = \frac{3}{4} \left[ 3^k \left( 2k-1\right)+1 \right]+(k+1)3^{k+1}=\frac{3}{4} \left[ 3^k \left( 2k-1\right)+1 +4(k+1)3^k\right]= \frac{3}{4} \left[ 3^k \left( 6k+3\right)+1 \right]=\frac{3}{4} \left[ 3^{k+1} \left( 2(k+1)-1\right)+1 \right]$, finishing the induction.

1

Hint $\ $ Prove by induction the closed form for $\rm \sum_{k=0}^n x^k,\:$ differentiate, then specialize $\rm\:x = 3.$

  • 2
    I don't know what the closed form is, how to differentiate it, or what it means to specialize it. However, after high school algebra I could solve the OP's problem. Whether the OP understands your answer or not, this answer fails to reach the general audience for answers to this question. Hard for me to believe someone could understand this answer and not be able to answer the OPs question.2012-04-21
  • 0
    I do not think this is the anticipated method, based on the form of the question, and the information given. (e.g. we're not given the closed form for $\sum{x^k}$)2012-04-21
  • 0
    @Ronald The closed form for a sum of a geometric series is well-known. Its proof by induction is much easier to discover than the proof of the given sum. To be successful at inductive proofs requires learning how to transform complicated inductions to simpler inductions. The above is one way to do so for the given sum. Introducing parameters, then differentiating etc. is a powerful tool popularized by Euler, and systemized more recently by combinatorists (generating functions, Umbral calculus, etc). Another way to simplify induction is to transform to a *telescopy*, as in my other answer.2012-04-21
  • 0
    @OldPro Out of curiosity, having just joined this site, why do you think that you are in a position to judge if answers "reach the general audience for answers to this question". fyi: Our users here span a wide range of mathematical expertise, from elementary school to research-level, averaging undergrad level. So it's not always easy to infer knowlegde-level. I am always happy to explain at length my answers. Simply let me know what points you'd like elaborated.2012-04-24
  • 0
    @Bill, please see the FAQ about [When *shoudn't* I comment](http://math.stackexchange.com/privileges/comment)2012-04-24
  • 0
    @OldPro My offer to explain things still stands in case you are interested in the mathematics.2012-04-24