2

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.

Yuval Filmus
  • 57,157
lampShade
  • 1,053
  • 1
    Did you ever try to write out what f(3) would be? Your recurse twice. – Leonidas Feb 01 '11 at 03:40
  • @Leonidas, my professor said mine was wrong so I have did not. – lampShade Feb 01 '11 at 03:43
  • 1
    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 01 '11 at 03:47
  • You are close. How about this: $f(1) = 1, f(n) = 1 + \frac{f(n-1)}{2}$. – Tpofofn Feb 01 '11 at 03:48
  • @Ross Millikan: Done. I was hoping/waiting for a response of lampShade but my intention was to do this eventually. – t.b. Feb 01 '11 at 05:22

1 Answers1

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.

t.b.
  • 78,116