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