Prove that the sum of $n$ integers starting from $n$ has the recurrence $a_{n-1}+3n-2;\quad a_0=0$
$$\sum_{i=n}^{2n-1}i=a_{n-1}+3n-2\quad n\in\mathbb{N} \tag{EQ 1}$$
Examples:$$n=1 \qquad \sum_{i=1}^{2\cdot (1)-1}i=1 \qquad a_{1-1}+3\cdot 1-2=0+3-2=1$$
$$n=2 \qquad \sum_{i=2}^{2\cdot (2)-1}i=(2+3) \qquad a_{2-1}+3\cdot 2-2=1+6-2=5$$
$$n=3 \qquad \sum_{i=3}^{2\cdot (3)-1}i=(3+4+5)\qquad a_{3-1}+3\cdot 3-2=5+9-2=12$$
This summation will make the pentagonal figurate numbers. Ignore that. Do not use $n(3n-1)/2.$ Prove that the summation is equivalent to the given recurrence using induction.
My attempt.
Show that EQ 1 is true for $n=1.$ This is already done in the Example.
Assume that EQ 1 is true for some arbitrary $k\in\mathbb{N}$
$$\left(\sum_{i=k}^{2k-1}i=a_{k-1}+3k-2\quad k\in\mathbb{N}\right)\longleftarrow \text{The inductive hypothesis}$$
Write "the form" for $a_{k+1}$
$$\sum_{i=k+1}^{2(k+1)-1}i = \left[a_{(k+1)-1}+3(k+1)-2\right] = a_k+3k+1$$
Pick the complicated side of "the form" and algebraically reduce it to get the other side. Usually the complicated side is the summation since it has more terms.
$$\sum_{i=k+1}^{2(k+1)-1}i = \sum_{i=k}^{2k-1}i + (k+1) \tag{EQ 2}$$
This is where I am stuck. EQ 2 should be the kth term + the $(k+1)^{th}$ term. My next step would be to use the inductive hypothesis to replace the RHS summation term with $a_{k-1}+3k-2$ and then algebraically derive $a_k+3k+1$ but I am not believing that EQ 2 is correct, and if it is, I don't know how to do the algebra. What have I done wrong?
