Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
@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

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.