<s>[INST] How do I get to this formula for this recursive sum and is my reasoning in proving this correct? I have the following sequence:
$n=1$ $$1$$
$n=2$ $$2+3+4$$
$n=3$ $$5+6+7+8+9$$
$n=4$ $$10+11+12+13+14+15+16$$
$$...$$
So abstracting these sums, we can write:
$n_1+(n_1+1)+...+(n_2-1)+n_2$
, where $n_1$ is the first term an $n_2$ is the last term of the sum.
And the sum of every $n^{th}$ term is:
$\frac{1}{2}(n_2-n_1+1)(n_1+n_2)$
Now I want to show that to calculate that the sum up to a certain $n$ value can be calculated as:
$$\frac{1}{2}n^2(n^2+1)$$
But I get stuck in finding this expression from the prior knowledge I described above.
I see it is closely related to the formula for the sum of nonnegative integers, but I can't figure out the line of reasoning that brings me to this formula for the sum of the above sequence for an $n^{th}$ value.
I could also try to proof that this formula is correct and I immediately thought of induction.
So we can first write
$$\frac{1}{2}(n_2-n_1+1)(n_1+n_2)$$
in terms of $n+1$, like:
$$\frac{1}{2}(n^2+1-(n+1)^2)(2n+1)$$
Then for the base case, $n=1$, we have
$$\frac{1}{2}1^2(1^2+1) = 1$$
Now for the inductive step, I started with:
$$f(n+1) = f(n) + \frac{1}{2}(n^2+1-(n+1)^2)(2n+1)$$
then proceded with the RHS as:
$$\frac{1}{2}n^2(n^2+1)+ \frac{1}{2}(n^2+1-(n+1)^2)(2n+1)$$
Now, to get the inductive step to work, we need to end up with:
$$f(n+1) = \frac{1}{2}(n+1)^2((n+1)^2+1)$$
But I don't see how we can proceed from where I've finished. I can do some algebraic manipulations, but it doesn't brings me to the above equation.
So my questions are:

*

*For the first part: how can I show that the sum of the sequence for a given $n$ is equal to $$\frac{1}{2}n^2(n^2+1)$$


*For the second part/the proof by induction part:



*

*Is my reasoning and are my calculations up to this point correct (in order to prove the thing that I want to prove)?


*If yes, how can I continue to get my inductive step to work. And if no, where are my calculations incorrect or when the reasoning is incorrect, how can I prove, perhaps via an alternative route, that the sum up to a certain $n$-value is indeed calculated as:
$$\frac{1}{2}n^2(n^2+1)$$
 [/INST] The sum is equal to the sum of integers up to $n^2$ which is trivially given by $\frac{1}{2}n^2(n^2+1)$, then we could prove at first the general result by induction and then use it for this particular case.
Refer also to the related

*

*Proof $1+2+3+4+\cdots+n = \frac{n\times(n+1)}2$

Edit
Following your way, for the inductive step we have
$$\frac{1}{2}n^2(n^2+1)+\overbrace{(n^2+1)+(n^2+2)+\ldots+(n+1)^2}^{2n+1\: \text{terms}}=$$
$$=\frac{1}{2}n^2(n^2+1)+n^2(2n+1)+\frac12(2n+1)(2n+2)=$$
$$=\frac{1}{2}n^2(n^2+1)+\frac{1}{2}n^2(2n+1)+\frac{1}{2}n^2(2n+1)+\frac12(2n+1)(2n+2)=$$
$$=\frac{1}{2}n^2(n^2+1+2n+1)+\frac{1}{2}(2n+1)(n^2+2n+2)=$$
$$=\frac12 (n^2+2n+1)(n^2+2n+2=\frac12 (n+1)^2+((n+1)^2+1)$$
</s>