# Difficulties in a proof by mathematical induction (involves evaluating $\sum r3^r$).

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.

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}

• -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. – Bill Dubuque Apr 21 '12 at 19:38
• @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. – Asaf Karagila Apr 21 '12 at 19:42
• @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". – Asaf Karagila Apr 21 '12 at 19:50
• @Bill: I have taught induction to hundreds in the past two years. I am fairly confident in my ability to choose my answers. – Asaf Karagila Apr 21 '12 at 19:56
• @Mob What if $\frac{1}{r(r+1)}$ is just $\frac{1}{r}-\frac{1}{1+r}$? – Vadim Apr 22 '12 at 0:32

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.

• 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. – Asaf Karagila Apr 21 '12 at 19:25
• @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. – F M Apr 21 '12 at 19:26
• 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. – Vadim Apr 21 '12 at 19:42
• @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. – Asaf Karagila Apr 21 '12 at 19:46
• Please I am a student. Trying to learn the basics. This is way too advanced for me. – Mob Apr 21 '12 at 22:11

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.

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$.

• Thanks but I don't understand. Please I'm trying to learn. – Mob Apr 21 '12 at 19:07
• @Mob: What is it that you don't understand? – F M Apr 21 '12 at 19:08
• The method Fernando used is called strong induction. Similar but different to the mathematical induction you are used to. Google or wikipedia it – Adam Rubinson Apr 21 '12 at 19:08
• This is advanced. I'm looking for the normal method, with explanations if possible. – Mob Apr 21 '12 at 19:12
• Strong induction is not neccessary (i.e. "holds for all $n \leq N$" can be replaced by "holds for $n=N$") – sdcvvc Apr 21 '12 at 19:12

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

• 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. – Old Pro Apr 21 '12 at 20:33
• 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}$) – Ronald Apr 21 '12 at 20:34
• @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. – Bill Dubuque Apr 21 '12 at 20:45
• @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. – Bill Dubuque Apr 24 '12 at 2:42
• @Bill, please see the FAQ about When shoudn't I comment – Old Pro Apr 24 '12 at 4:01