On the inductive step in the proof by induction that $\sum_{j=1}^n(4j-1)=n(2n+1)$

Question

How can I prove this by induction? I am stuck when there is a $\Sigma$ and two variables, how would I do it? I understand the first step but have problems when i get to the inductive step.

$$\sum_{j=1}^n(4j-1)=n(2n+1)$$

Answer 1

The only variable in the expression is $n$. If you denote the sum on the left by $s(n)$, you need to prove that $s(1)=3$ and that if $s(n)=n(2n+1)$ then $s(n+1)=(n+1)(2(n+1)+1)$.

Note that $s(n+1)=\sum\limits_{j=1}^{n+1}(4j-1)=(4(n+1)-1) + \sum\limits_{j=1}^{n}(4j-1)$.

Answer 2

First of all, you would start off with the basis step.

Basis step

The base value is 1, and we need to check both sides of the equation.

$4*1-1 = 1*(2*1+1) \implies 3 = 3$

Therefore, as it can be seen, the equation holds for the base value. Now, we use the inductive step to check if the equation holds for $k + 1$, where $1 \leq k \leq n$.

Inductive step

We will test for the equation

$\sum_{j = 1}^{k} (4j - 1) + (4(k+1) - 1) = (k+1)(2(k+1)+1) = (k+1)(2k+3) = 2k^2 + 5k + 3$

By induction, we want to achieve the right-hand-side equation.

By the hypothesis, we can exchange the sigma part of the left-hand-side equation.

$k(2k + 1) + (4(k+1)-1) = 2k^2 + k + (4k+3) = 2k^2 + 5k + 3$

As it can be seen, we have now reached the same right-hand-side as in our equation for $k+1$. Therefore, we have hereby proved the equation by induction.