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.

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.

share|improve this question
1  
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
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 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
show 1 more comment

1 Answer

up vote 6 down vote accepted

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.

share|improve this answer
    
A great answer. I wish I could upvote more than once. –  Ross Millikan Feb 1 '11 at 5:26
    
@Ross Millikan: Thanks! –  t.b. Feb 1 '11 at 5:27
add comment

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.