Solving a nonhomogeneous linear recurrence relation

Question

Let's have a look at this supposedly simple relation: $$ \begin{cases} f(n)=2\cdot f(n-1)+n \\ f(1)=1 \end{cases} $$

After a few expansions, for $n=5$, we get

$$ \begin{align} f(5)&=2(2(2(2f(1)+2)+3)+4)+5) \\ &=2^4f(1)+\sum_{i=0}^{3}{2^i\cdot (5-i)} \end{align} $$

So, we can generalize to $$ f(n)=2^{n-1}+\sum_{i=0}^{n-2}{2^i\cdot (n-i)} $$

After that, I still couldn't arrive at the final solution, without any sum terms.

So, using only elementary tools (i.e without generating functions, etc.), how can one solve this relation?

Answer 1

Looking at homogenous equation $f(n) = 2f(n-1)$, we get $f(n) = A \cdot 2^n$ for some constant $A \in \mathbb R$ is our general solution to that equation.

Now we want to find one solution to equation $f(n) = 2f(n-1) + n$.

Looking at the remaining $n$, we can guess it should be some sort of linear, so let's try $f_*(n) = an+b$, where by $f_*$ I denote special solution.

Then we have $an + b = 2a(n-1) + 2b + n$ which is equivalent to: $n(a+1) + b -2a = 0$

It must holds for any $n \in \mathbb N$, so we need $(a+1) = 0$, that means $a=-1$ and $b-2a = 0$, so $b = 2a = -2$

So our special solution is $f_*(n) = -n-2$.

Now, any solution to our system of equation is of the form : general solution + special solution.

So plugging it in, we have our solution to be $f(n) = A\cdot 2^n -n - 2$.

Plugging $f(1) = 1$, to get the value of $A$, we have:

$1 = 2A - 1 - 2$, so $A=2$

And our solution is $f(n) = 2^{n+1} - n - 2$

Answer 2

We try to write $f(n)=g(n)+h(n)$ where$$g(n)-2g(n-1)=n$$$$h(n)-2h(n-1)=0$$

Now $h(n)$ is easy with $h(n)=2^nh(0)$ - but we don't know what $h(0)$ is yet.

For forms like this with a polynomial in $n$ on the right-hand side, we try a solution with $g(n)$ being a polynomial of the same degree [there are special cases where a higher degree is necessary].

So here we want $g(n)=an+b$ to be linear.

We call $g(n)$ a particular solution, and $h(n)$ a solution of the "homogeneous part".

That should be enough clue for you to try to finish it yourself.

Note: Generally the unknowns in the particular solution will be determined direct from the recurrence, while those in the homogeneous part (which represents the degrees of freedom in the solution) will be found by reference to the initial conditions.

Answer 3

Your recurrence relation is linear, but not homogeneous.

One approach is as follows: begin by solving the homogeneous recurrence relation, $$ f(n) = 2 f(n - 1). $$ We end up with a general solution of $f_H(n) = C2^n$. Now, it suffices to find one "particular solution" to the original non-homogeneous difference equation. Following the method of undetermined coefficients, we take the ansatz $$ f(n) = an + b \implies\\ f(n-1) = an + (b-a). $$ Plugging this in to our recurrence relation yields $$ f(n) = 2 f(n - 1) + n \implies an + b = 2[an + (b-a)] + n\implies\\ an + b = (2a+1)n + 2b-2a \implies\\ (a + 1)n + (2a-b)= 0 $$ So, $a = -1$, $b = -2$ will work. We can therefore take $ f_P(n) = -n-2. $ Thus, our general solution is $$ f(n) = f_H + f_P = C \,2^n - n - 2. $$ Using the initial conditions, solve for $C$.

Answer 4

Divide both parts by $2^n$ and you have a linear recurrence

$$\frac{f(n)}{2^n}=\frac{f(n-1)}{2^{n-1}}+\frac{n}{2^n}$$

$$\frac{f(n)}{2^n}-\frac{f(n-1)}{2^{n-1}}=\frac{n}{2^n}$$

This is a telescopic term then you can apply the summation in both parts

$$\sum_{n=2}^{m}\frac{f(n)}{2^n}-\frac{f(n-1)}{2^{n-1}}=\sum_{n=2}^{m}\frac{n}{2^n}$$

$$\frac{f(m)}{2^m}-\frac{f(1)}{2}=\frac{3}{2}-\frac{m+2}{2^m}$$

$$f(m)=2^{m+1}-m-2$$

Answer 5

$$ \begin{align} f(n)&=2f(n-1)+n\tag1\\ f(n)+(n+2)&=2(f(n-1)+(n+1))\tag2\\ g(n)&=2g(n-1)\tag3 \end{align} $$ Explanation:
$(1)$: original recursion
$(2)$: add $n+2$ to both sides
$(3)$: let $g(n)=f(n)+(n+2)$

Starting with $g(1)=f(1)+3=4$, we get $$ g(n)=2^{n+1}\tag4 $$ and therefore, $$ f(n)=2^{n+1}-n-2\tag5 $$