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
I'm looking over the solution to a test problem on recurrence relations, and I am stuck. I can't figure out the jump that was made.
All that it says is "To simplify the algebra, do an index shift: " $$\sum_{i=n^2-3}^{n^2+n-4} (i+4) = \sum_{i=1}^{n} (n^2+i)$$
What was done here?
One possible source of confusion is the use of $i$ as the summation index on both sides. That is correct ($i$ is a dummy index and you can rename it at will as long as you are consistent about the renaming), but it might be easier to proceed in steps where you define a new summation index in terms of the old one and then, at the very end, you do the renaming.
E.g. in this case, consider the sum
$$ \sum_{i=n^2-3}^{n^2+n-4} (i+4) $$
Let's start with a small step: define $j = i + 3$ in order to eliminate that pesky $-3$ in the lower limit. In terms of $j$, the lower limit becomes $j = n^2$, the upper limit becomes $j = n^2+n-1$ and the summand becomes $(j+1)$, so we get
$$ \sum_{i=n^2-3}^{n^2+n-4} (i+4) = \sum_{j=n^2}^{n^2 + n - 1} (j + 1) $$
Working on the RHS, define $k = j - n^2$. That makes the lower limit $k=0$, the upper limit $n-1$ amd the summand $(k + n^2 + 1)$, so we have
$$ \sum_{j=n^2}^{n^2 + n - 1} (j + 1) = \sum_{k=0}^{n-1}(k+n^2 + 1) $$
Now rename $k$ to $i$ on the RHS and ... oops! I just went back and saw that you wanted the lower limit to be $1$ instead of $0$. No matter: we can do another transformation: $l = k + 1$, so the lower limit becomes $l = 1$, the upper limit becomes $l = n$ and the summand becomes $(l + n^2)$. We get
$$ \sum_{k=0}^{n-1}(k+n^2 + 1) = \sum_{l=1}^{n}(l + n^2) $$ Now rename the dummy index $l$ to $i$ and you get your RHS.
Obviously, you could do it all in two steps: $j = i - (n^2 - 3) + 1$ and then doing the rename, but maybe the multiple steps help.
And writing out the first few terms and the last couple of terms on each side will help to clarify what is going on.
This is the special case of $$\sum_{i=a}^b f(i+c)=\sum_{i=a+c}^{b+c}f(i)$$with $$a:=n^2-3,\,b:=n^2+n-4,\,c:=4-n^2,\,f(i):=n^2+i.$$
Observe that substituting the lower limit into the LHS gives the same as substituting the lower limit into the RHS.
Substituting the upper limit into the LHS gives the same expression as substituting the upper limit into the RHS.
In each case, we are going up in increments of one, so the two summations precisely match.
Of course, you could have shifted by a different amount, to obtain a summation that looks different, but if you take care you can force equality in this way.
I'll leave you to check the details.
What was done here?
The index $i$ was replaced everywhere on $\text{LHS}$ by $i+n^2-4$ to get the neat sum on $\text{RHS}.$
Observe that the numbers being summed are: $$ \begin{matrix} i=.. & 1& 2& 3& 4\\ n=1& 2& & &\\ n=2& 5& 6& &\\ n=3& 10& 11& 12&\\ n=4& 17& 18& 19& 20 \end{matrix} $$ This is OEIS sequence A004202 "Skip 1, take 1, skip 2, take 2, skip 3, take 3, etc.".
The simplest way to describe this is as $\ \sum_{i=1}^n n^2+i.$
Use the index shift method in complicated situations, but it is not required here.
