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

-
Did you ever try to write out what f(3) would be? Your recurse twice. –  Leonidas Feb 1 '11 at 3:40
@Leonidas, my professor said mine was wrong so I have did not. –  lampShade Feb 1 '11 at 3:43
As Leonidas suggests, your formula doesn't work for stupid reasons (do try it for $n = 3$). Also, your last summand should be $\frac{1}{2^{n-1}}$ instead of $\frac{1}{n}$. However, what you can do is to define $f(1) = 1$ and $f(n) = 1 + \frac{1}{2}f(n-1)$. Maybe that's what you have in mind. –  t.b. Feb 1 '11 at 3:47
You are close. How about this: $f(1) = 1, f(n) = 1 + \frac{f(n-1)}{2}$. –  Tpofofn Feb 1 '11 at 3:48
@Theo Buehler: Please post as an answer so it can be accepted. That way this gets closed. –  Ross Millikan Feb 1 '11 at 5:00

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.