# Use the recursive definition of summation together with mathematical induction to prove a sequence

Use the recursive definition of summation together with mathematical induction to prove that for all positive integers $n$ if $a_1, a_2,\ldots, a_n$ are real numbers, then

$$\sum_{k=1}^n(3a_k - 2k + 3) = 3\sum_{k=1}^na_k - n^2 + 2n.$$

Attempted Solution: I know how to check the base case ($n = 1$) of both the left and the right side to get $3a_1 + 1$.

For my inductive hypothesis, I got:

Assume for $j \ge1$, $\sum_{k=1}^j(3a_k - 2k + 3) = 3\sum_{k=1}^ja_k - j^2 + 2j$.

From the recursive definition of summation: $S_{j+1}= S_j + a_{j + 1}$.

After this I am lost. I don't know where to start, and unfortunately, my professor didn't have any notes about proving these with mathematical induction. Looking at the solutions manual I am even more confused. If anyone can look at his solution and kind of go step by step with me to tell me what he did or where he got things from, I would seriously appreciate it. I am especially having trouble knowing with what equations to set things up with, and how to change the $j$ on sigma to $j + 1$.

Teachers Solution:

\begin{align} S_{j+1} &= S_j + a_{j+1}\\ &=\sum_{k=1}^j(3a_k - 2k + 3) + 3a_{j+1}-2(j+1)+3\\ &= 3\sum_{k=1}^ja_k - j^2 + 2j + 3a_{j+1}-2(j+1)+3\\ &= 3\sum_{k=1}^{j+1}a_k - j^2 + 2j -2(j+1)+3\\ &= 3\sum_{k=1}^{j+1}a_k - (j+1)^2 + 2(j+1)\\ &=\text{Right Side}_{j+1} \end{align}

Therefore, $\sum_{k=1}^n(3a_k - 2k + 3) = 3\sum_{k=1}^na_k - n^2 + 2n.$.

Thank you for any help..

The teacher's solution is somewhat problematic in itself as it (ab)uses $a_j$ for two purposes: Once for the "generic" name of the summand in the first line $S_{j+1}=S_j+a_{j+1}$ and then as the numbers from which the summands are computed via $3a_k-2k+3$. Of course in general $a_{j+1}\ne3a_{j+1}-2(j+1)+3$!

I guess the most promising way to prove equations about such summations is as follows: Consider the left hand side and the right hand side as functions of $n$, say $f(n)=\sum_{k=1}^n(3a_k-2k+3)$ and $g(n)=3\sum_{k=1}^na_k-n^2+2n$. Then show that $f(1)=g(1)$ (you did that). Next concentrate on one side and compute $f(n)-f(n-1)$ for $n>1$, making use of the recursive definition: \begin{align}f(n)-f(n-1)&=\sum_{k=1}^{n}(3a_k-2k+3)-\sum_{k=1}^{n-1}(3a_k-2k+3)\\&= \left(\sum_{k=1}^{n}(3a_k-2k+3)+(3a_n-2n+3)\right)-\sum_{k=1}^{n-1}(3a_k-2k+3)\\&=3a_n-2n+3.\end{align} Do the same with the right hand side: \begin{align}g(n)-g(n-1)&=\left(3\sum_{k=1}^na_k-n^2+2n\right)-\left(3\sum_{k=1}^{n-1}a_k-(n-1)^2+2(n-1)\right) \\ &=\left(3\sum_{k=1}^{n-1}a_k+3a_n-n^2+2n\right)-\left(3\sum_{k=1}^{n-1}a_k-(n-1)^2+2(n-1)\right) \end{align} and simplify until you notice that this is just $f(n)-f(n-1)$.

• Since Fn+1 = Fn + Fn-1 by definition, why are we not using f(n) + f(n-1)? Is there a definition that allows us to use f(n) - f(n-1)?
– Alex
May 3, 2014 at 10:01

Only a hint to make things easyer:

$$\sum_{k=1}^{n}(3a_{k}-2k+3)=3\sum_{k=1}^{n}a_{k}-n^{2}+2n$$ is clearly a direct consequence of: $$\sum_{k=1}^{n}\left(-2k+3\right)=-n^{2}+2n$$

Simply because: $$\sum_{k=1}^{n}3a_{k}=3\sum_{k=1}^{n}a_{k}$$ and this term can be added or subtracted on both sides.