How to find explicit formula using backwards iteration

Question

For this problem I tried to solve it by iterating downward so:

a_n = a_n-1 - n

a_n-1 = 2*(2a_n-2 - (n-1)) - n = 4a_n-2 - 3n + 2

a_n-2 = 2*(4a_n-3 - 3n + 2) - n = 8a_n-3 - 7n + 4

a_n-3 = 2*(8a_n-4 - 7n + 4) - n = 16a_n-4 - 15n + 8

Then I figured that this could be rewritten in this format:

2^k+1a_n-k - (2^k+1 - 1)n + 2^k

And then I believe that I am supposed to rewrite this equation using the sigma notation, but I'm not sure if I did the steps correctly because I don't understand how to rewrite what I have found in the form outline in the problem.

Answer 1

Hint:

$$\begin{align} a_n&=2a_{n-1}-n\\ 2a_{n-1}&=4a_{n-2}-2(n-1)\\ 4a_{n-2}&=8a_{n-3}-4(n-2)\\ \vdots\\ 2^{n-1}a_{1}&=2^{n}a_{0}-2^{n-1}(1)\\ \end{align}$$ by summing all steps

$$a_n=2^{n}a_0-\sum_{i=0}^{n-1}2^{i}(n-i)$$

$$a_n=3\cdot2^{n}-\sum_{i=0}^{n-1}n2^{i}+\sum_{i=0}^{n-1}i2^{i}$$

$$a_n=3\cdot2^{n}-n\sum_{i=0}^{n-1}2^{i}+\sum_{i=0}^{n-1}i2^{i}$$