1

The perturbation method is useful for evaluating sums like $\sum_{k=0}^{n}{a_k}$, but every example I've found is a case where $a_k$ is a sequence dependent only upon the index variable $k$.

It is explained that we set $S_n=\sum_{k=0}^{n}{a_k}$ and then solve the equation $S_n+a_{n+1}=a_0+\sum_{k=1}^{n+1}{a_k}$ for $S_n$. But I never stumbled upon a sum that would be of the form, e.g. $\sum_{k=0}^{n}{kn}$ solved using this particular method, and when I tried doing it myself I got confused with how should I treat a boundary inside a sum when I can't just factor it out.

I set $S_n=\sum_{k=0}^{n}{kn}$, but as to other terms, I don't know what to do. Is $a_{n+1}=n(n+1)$ or $(n+1)^2$? Is the right side $\sum_{k=0}^{n+1}{kn}$ or $\sum_{k=0}^{n+1}{k(n+1)}$? Why? (also let's assume we can't factor out the $n$, as if we had summing over $f(kn)$)

Irregardless
  • 469
Joald
  • 625
  • except if f is multiplicative we might be able to factor the contribution by n out. –  Aug 07 '17 at 20:56

1 Answers1

2

When looking at the expression \begin{align*} S_n=\sum_{k=0}^n kn\tag{1} \end{align*} the symbol $n$ on both sides identifies one and the same variable $n$. This means that substitution of the symbol $n$ by $n+1$ has to be done at each occurrence of $n$ at both sides simultaneously.

We obtain \begin{align*} S_{n+1}&=\sum_{k=0}^{n+1}k(n+1)=(n+1)\sum_{k=0}^{n+1}k\tag{2}\\ &=\left(\sum_{k=0}^n k(n+1)\right)+(n+1)^2 \end{align*}

Note that in (2) we do not have the same situation as in (1), namely \begin{align*} S_n=\sum_{k=0}^n a_k \end{align*} but rather a generalisation in the form \begin{align*} S_n=\sum_{k=0}^n a_{k,n} \end{align*} and again we obtain by substituting $n+1$ for $n$ \begin{align*} S_{n+1}=\sum_{k=0}^{n+1} a_{k,n+1} \end{align*}

Markus Scheuer
  • 108,315