# solving linear non homogeneous recursive relation.

I'm having trouble solving this relation: $$a_n = a_{n-1} + 2^{n-1} - 1$$ as a part of my university assignment.

My intention was to start with finding the $$a_{n}^{h}$$, and for that I've tried finding a characteristic equation for the homogeneous part of equation ($$0 = a_{n} - a_{n-1}$$). Solving $$0 = x - 1$$ left me with a single root $$r_1 = 1$$, and hence the $$a_{n}^{h} = \alpha(1^n)$$.

Then I tried to find the $$a_{n}^{p}$$, and for that I was advised to solve independently for $$a_{n} - a_{n-1} = -1$$ and $$a_{n} - a_{n-1} = 2^{n-1}$$, and to add the acquired results to obtain $$a_{n}^{p}$$.

So I tried to start by solving $$2^{n-1} = a_{n} - a_{n-1}$$. I thought that first expressing $$2^{n-1}$$ as $$\frac{1}{2}(2^n)$$, will allow me to use $$\frac{A}{2}(2^n)$$ for my guessed form, and so substituted it into the equation obtaining: $$\frac{A}{2}(2^n) = \frac{A}{2}(2^n) - \frac{A}{2}(2^{n-1})$$, and then I tried to simplify it by first expressing the second term in the difference as $$\frac{A}{4}(2^n)$$, and then dividing the equation by $$2^n$$, and sequentially multiplying by 2 which left me with $$A = A - \frac{A}{2}$$, which made zero the only valid solution.

Then I tried to solve $$-1 = a_n - a_{n-1}$$. Since -1 is a constant I replaced it with $$A$$, and solved the following equation $$A = A - A$$ (here I was very confused, but it was the only way constant substitution made sense to me), so this also leaves zero as the only possible value.

Then combining $$a_{n}^{h}$$ and $$a_{n}^{p}$$ yielded $$a_n = \alpha(1^n) + 0$$, leaving me with just $$a_n = \alpha(1^n)$$, and at this point given the initial conditions $$a_0 = a_1 = 0$$, I've decided to solve for alpha and to no surprise also got zero.

At this point I saw that solution was horribly wrong, and absolutely had no clue where because to be honest none of it is perfectly clear to me, but to verify that its certainly wrong I made a rust script to calculate first 10 terms of the sequence which definitely weren't zeroes. Here it is, just in case.

Any help would be appreciated but I would be grateful even more if you could point flaws in my process (I know that there are quite a few, so hopefully there are patient people), rather then providing some from the blank solution.

• Hint: $a_n = (a_n - a_{n-1}) + (a_{n-1} - a_{n-2}) + \cdots + (a_2 - a_1) + a_1= (2^{n-1} - 1)+(2^{n-2} - 1) + \cdots +(2^1 - 1) + a_1$. Can you simplify this geometric sum? Commented Dec 12, 2021 at 7:46

\begin{align} a_n &= a_{n-1} + 2^{n-1} - 1 \\ \iff\;\;\;\;(a_n+n)& = (a_{n-1}+n-1) + 2^{n-1} \\ \iff\;\;\;\;\frac{a_n+n}{2^n}& = \frac{1}{2} \cdot \frac{a_{n-1}+n-1}{2^{n-1}} + \frac{1}{2} \\ \iff\;\;\;\; \frac{a_n+n}{2^n} - 1 &= \frac{1}{2}\left(\frac{a_{n-1}+n-1}{2^{n-1}}-1\right) \end{align}
The latter equality means that $$\displaystyle\,\frac{a_n+n}{2^n} - 1 \,$$ is a geometric progression.
It is clear from the definition that $$\begin{eqnarray*} a_n&=&a_{n-1}+(2^{n-1}+1)\\ &=&a_{n-2}+(2^{n-2}+1)+(2^{n-1}+1)\\ &\vdots&\\ &=&a_0+\sum_{k=0}^{n-1}(2^k-1). \end{eqnarray*}$$ Of course the latter sum is easily evaluated, if you know the closed form of a geometric sum: $$\sum_{k=0}^{n-1}(2^k-1)=-n+\sum_{k=0}^{n-1}2^k=-n+(2^n-1)=2^n-n-1.$$