Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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}$$
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.
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$.
Hint $\ $ Prove by induction the closed form for $\rm \sum_{k=0}^n x^k,\:$ differentiate, then specialize $\rm\:x = 3.$
