2
$\begingroup$

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.

  • 0
    @Ross Millikan: Done. I was hoping/waiting for a response of lamp$S$hade but my intention was to do this eventually. – 2011-02-01

1 Answers 1

6

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.

  • 0
    @Ross Milli$k$an: Than$k$s! – 2011-02-01