# solving inhomogeneous recurrence relation

I had encountered an inhomgeneous equation of the type :

$$f(n)=h(f(n))+g(n)$$

below is the equation.

$$f(n)=\begin{cases} f(n-1)+2^{(n-1)/2},&\text{if }n\text{ is odd}\\\\ f(n-1)+2^{n/2},&\text{if }n\text{ is even}\;. \end{cases}$$

I read various methods of solving such recurrences and found that it can be solved by individually solving $f(n)$ and $g(n)$ and then summing both the solutions. I tried my best to do on my own but unsuccessfully. please help me in finding out the correct solution.

initial conditins $f(1)=2$.

-
@brian : thnx for editing – sandyroddick Sep 5 '12 at 2:52
Is the first equation supposed to be for $f(n + 1)$? – Tunococ Sep 5 '12 at 2:52
Just an observation: The second initial condition is redundant. – Tunococ Sep 5 '12 at 2:55
@Tunococ : are you asking for the odd one...yeah i noticed its redundant – sandyroddick Sep 5 '12 at 2:56
Should the first equation be $f(n+1)=f(n)+g(n)?$ – Ross Millikan Sep 23 '12 at 17:42

It never hurts to gather some computational data first; sometimes it leads to a quick and easy guess at the answer, which can then be proved rigorously.

$$\begin{array}{r|c} n:&1&2&3&4&5&6&7&8&9&10\\ f(n):&2&4&6&10&14&22&30&46&62&94\\ \text{Increase}:&&2&2&4&4&8&8&16&16&32 \end{array}$$

A look at that last line, showing the amount of increase from one term to the next, makes it pretty clear that $$f(2n+1)=2+2\left(2^1+2^2+\ldots+2^n\right)=2+2\sum_{k=1}^n2^k=2\sum_{k=0}^n2^k$$ and $$f(2n+2)=f(2n+1)+2^{n+1}=2\sum_{k=0}^n2^k+2^{n+1}$$ for $n\ge 0$.

From the formula for the sum of a geometric progression we know that $\sum_{k=0}^n2^k=2^{n+1}-1$, so conjecture that

\begin{align*} f(n)&=\begin{cases} 2\left(2^{(n+1)/2}-1\right),&\text{if }n\text{ is odd}\\\\ 2\left(2^{n/2}-1\right)+2^{n/2},&\text{if }n\text{ is even} \end{cases}\\\\ &=\begin{cases} 2^{(n+3)/2}-2,&\text{if }n\text{ is odd}\\\\ 3\cdot2^{n/2}-2,&\text{if }n\text{ is even}\;. \end{cases} \end{align*}

Now that we’ve discovered what the correct closed form almost certainly is, we can prove it by induction on $n$. I’ll leave that part to you.

There are more systematic approaches. In fact, after going through this argument you might well discover on your own that in general if $f(n)=f(n-1)+g(n-1)$, then

\begin{align*} f(n)&=f(n-1)+g(n-1)\\ &=\Big(f(n-2)+g(n-2)\Big)+g(n-1)\\ &=\Big(f(n-3)+g(n-3)\Big)+g(n-2)+g(n-1)\\ &\;\vdots\\ &=f(1)+g(1)+g(2)+\ldots+g(n-2)+g(n-1)\\ &=f(1)+\sum_{k=1}^{n-1}g(k)\;. \end{align*}

(This can be properly proved by induction.) Thus, if $g$ is any function for which you can find a closed form for $\sum_{k=1}^{n-1}g(k)$, you’re home free. In the specific problem we simply got a geometric series.

-
thank u very much...that was very insightful. – sandyroddick Sep 5 '12 at 3:49

I'll just assume the equation is of the form

$$f(n + 1) = f(n) + g(n)$$

where $g$ is given.

You can prove by induction that $f(n) = f(1) + \sum_{i=1}^{n-1} g(i)$. In this case, you are given $f(1) = 2$ and

$$g(n) = \begin{cases} 2^{n/2} & ; \text{n is even} \\ 2^{(n+1)/2} & ; \text{n is odd} \end{cases}$$

If $n$ is odd, you get

\begin{align*} f(n) & = f(1) + \sum_{i=1}^{n-1} g(i) \\ & = f(1) + \sum_{i=1}^{(n-1)/2}g(2i) + \sum_{i=1}^{(n-1)/2} g(2i - 1) \\ & = 2 + \sum_{i=1}^{(n-1)/2}2^i + \sum_{i=1}^{(n-1)/2}2^i \\ & = 2 + 2\sum_{i=1}^{(n-1)/2}2^i. \end{align*} I'll let you do the sum and the case where $n$ is even.

-