Summation by parts (finite calculus) of $\sum\limits_{i=0}^{n}i\cdot a^i$

Question

I'm studying the calculus of finite differences and have read about summation by parts:

$\sum f(x)\Delta g(x) = f(x)g(x) - \sum g(x+h)\Delta f(x)$.

The tutorials I'm using go a bit woolly at the point of introducing this technique: they use examples where they set $\Delta g(x)$ to $2^x$, and don't really show how to use it for anything a bit harder. I'm at a loss for basic examples.

I wondered if it is possible to determine

$S.n = \sum\limits_{i=0}^{n}i\cdot a^i$

using summation by parts? If so, how is it done?

Thanks in advance.

Answer 1

I find if I'm not sure about something, it's helpful to try and build it from first principles, looking up stuff if I get stuck.

For summation by parts, I know it's something like integration by parts, but with derivatives replaced by differences and integrals by sums, so it'll look something like $$ \sum_a^b f_k (g_k-g_{k-1}) = \text{{boundary terms}} - \sum_a^b g_k (f_k-f_{k-1}), $$ up to getting the indices wrong. I also remember that $\Delta f_k = f_k-f_{k-1} $ satisfies something like the product rule, which is why this works in the first place: we have $$ \Delta f_k g_k = f_k g_k - f_{k-1} g_{k-1} = (f_k-f_{k-1}) g_k + f_{k-1} (g_k-g_{k-1}) = g_k \Delta f_k + f_{k-1} \Delta g_k $$ by fiddling the terms to make it work: in particular, I notice that the indices were wrong in my initial guess. Now I just sum this from $k=a$ to $k=b$, to get $$ f_b g_b - f_{a-1} g_{a-1} = \sum_{k=a}^b g_k \Delta f_k + \sum_{k=a}^b f_{k-1} \Delta g_k, $$ and pushing one of these to the other side gives the formula $$ \sum_{k=a}^b g_k \Delta f_k = (f_b g_b - f_{a-1} g_{a-1}) - \sum_{k=a}^b f_{k-1} \Delta g_k. $$

---

Okay, now I've remembered what the formula is, let's apply it. I know how to sum $a^k$, but not $k a^k$ (well, I do, but let's pretend I don't for the purpose of the exercise), and if $g_k = k$, we obviously have $ \Delta g_k = 1 $, so this looks like the way to go. Therefore I'm going to have to take $\Delta f_k = a^k$. Of course I know a way to go from here to a valid $f_k$: $$ f_k = f_0 + \sum_{j=1}^k \Delta f_j = f_0 + \sum_{j=1}^k a^j = f_0+\frac{a^{n+1}-a}{a-1}, $$ and taking $f_0=a/(a-1)$ gives the nice $f_k=a^{k+1}/(a-1)$. We can choose a different $f_0$, but it'll cancel out everywhere because the sum of $f_0 \Delta g_k$ telescopes and cancels with the contribution to the boundary terms, so let's make life easier to start with. Now, putting everything in that we've learnt so far, $$ \sum_{k=1}^{n} k a^k = \frac{a^{n+1}}{a-1} n - 0 - \sum_{k=1}^n \frac{a^{k+1-1}}{a-1} 1 = \frac{ka^{k+1}}{a-1} - \frac{1}{a-1} \sum_{k=1}^n a^{k}, $$ and the latter sum we know; we end up with $$ \sum_{k=1}^{n} k a^k = \frac{na^{n+1}}{a-1} - \frac{a^{n+1}-a}{(a-1)^2}, $$ which thankfully is also precisely $$a\frac{d}{da}\frac{a^{n+1}-a}{a-1},$$ which does require some algebraic massaging to show, but is not too bad.

Answer 2

This is probably not an answer to your question.

I don't know about using summation by parts. However, here's another way \begin{align} \sum^n_{k=1}ka^k = a\sum^n_{k=1} ka^{k-1} = a\frac{d}{da}\left(\sum^n_{k=0} a^k\right) = a\frac{d}{da}\left(\frac{1-a^{n+1}}{1-a}\right) = a\frac{(1-a)(-(n+1)a^n)+(1-a^{n+1})}{(1-a)^2}. \end{align}