Basic Recursion Im trying to write recursive formulas for sequences but it seems like there are different techniques depending on what type of sequence I'm dealing with. for example I want to the sequence:
$1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} +.... \frac{1}{n}$ 
What I see when I look at this is all the next terms are $\frac{1}{2}$ the previous term. So, I wrote the following recursive formula - which is incorrect.
$f(1) = 1, f(n) = f(n-1) + \frac{f(n-1)}{2}$ Why is this wrong? 
Why is this correct? $f(1) = 1, f(n) = f(n-1) +\frac{1}{2}^{n-1}$
Intuitively I thought that my original attempt looked correct. 
 A: As Leonidas suggests, your formula doesn't work (let's try it for $n=3$):
\begin{align*}
f(2) & = f(1) + \frac{f(1)}{2} = 1 + \frac{1}{2} = \frac{3}{2} \\
f(3) & = f(2) + \frac{f(2)}{2} = \frac{3}{2} + \frac{\frac{3}{2}}{2} = \frac{9}{4} \neq 1 + \frac{1}{2} + \frac{1}{4} = \frac{7}{4}.
\end{align*}
Your last summand in $f(n) = 1 + \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^{n-1}}$ should be $\frac{1}{2^{n−1}}$ instead of $\frac{1}{n}$ (in the denominator there always is a power of $2$). If you write it this way then the "recursion" $f(n) = \left(1 + \frac{1}{2} + \cdots + \frac{1}{2^{n-2}}\right) + \frac{1}{2^{n-1}} = f(n-1) + \frac{1}{2^{n-1}}$ should be clear. But writing the parentheses in a different way yields
\begin{align*}
f(n) & = 1  + \left(\frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^{n-2}} + \frac{1}{2^{n-1}}\right) \\
& = 1 + \frac{1}{2}\left(1 + \frac{1}{2} + \cdots + \frac{1}{2^{n-3}} + \frac{1}{2^{n-2}}\right) \\
& = 1 + \frac{1}{2} f(n-1).
\end{align*}
This shows that you can define $f(1)=1$ and $f(n)=1+\frac{1}{2}f(n−1)$ recursively, and this seems to be nicer and closer to what you tried to do.

One thing to take away from this: If you postulate a formula, you should check it for small values of $n$. If there's an obvious mistake, you'll catch it quickly and don't waste time trying to prove it. Playing with the formulas for small $n$ often gives you a feeling of what could or should be true.
