1
$\begingroup$

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$.

  • 0
    Should the first equation be $f(n+1)=f(n)+g(n)?$2012-09-23

2 Answers 2

4

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.

  • 0
    thank u very much...that was very insightful.2012-09-05
3

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.