News: Currently the LaTeX and hidden solutions on this blog do not work on Google Reader. Email me if you have suggestions on how to improve this blog!
Tuesday, 2 August 2011
Math GRE - #1
If $F(1) = 2$ and $F(n) = F(n-1) + \frac{1}{2}$ for all integers $n > 1$, then $F(101) =$
49
50
51
52
53
The closed form formula is $F(n) = 2 + \frac{n-1}{2} = \frac{n+3}{2}$. Thus, $F(101) = 52$ is the correct answer.
6 comments:
Post a Comment
This webpage is LaTeX enabled. To type in-line formulae, type your stuff between two '$'. To type centred formulae, type '\[' at the beginning of your formula and '\]' at the end.
Where do you get the closed formula?
@Richard:
The pattern becomes fairly clear if you write the first handful of terms. That's how I did it, at least
Here's another solution that was inspired by my previous encounters with recurrence relations.
You can derive a formula for f(n+k) by using F(n) = F(n-1) +1/2 and replacing n with n+1, then n+2, then n+3, etc. on both sides and then simplifying the right-hand side to something with F(n-1) (by backtracking).
A pattern forms and you'll see the formula F(n+k) = F(n-1)+ (k+1)/2, which can be further simplified to F(n+k) = F(n) + k/2 by solving for F(n-1) in the given function. The formula is easily proved by induction (if you really want to on a multiple choice test) and gives us the same answer of 52 when we let n=1 and k=100.
Of course, from my formula F(n+k) = F(n) + k/2, you can get F(0+k) = 3/2 + k/2 =(k+3)/2 very easily if you merely solve for F(0) from the original function.
How do you get the closed form formula?
@affans:
I wrote out some terms in the series and guessed. Some of the comments above outline another approach to derive the formula.
6 comments:
Post a Comment
This webpage is LaTeX enabled. To type in-line formulae, type your stuff between two '$'. To type centred formulae, type '\[' at the beginning of your formula and '\]' at the end.
The pattern becomes fairly clear if you write the first handful of terms. That's how I did it, at least
You can derive a formula for f(n+k) by using F(n) = F(n-1) +1/2 and replacing n with n+1, then n+2, then n+3, etc. on both sides and then simplifying the right-hand side to something with F(n-1) (by backtracking).
A pattern forms and you'll see the formula
F(n+k) = F(n-1)+ (k+1)/2,
which can be further simplified to
F(n+k) = F(n) + k/2
by solving for F(n-1) in the given function. The formula is easily proved by induction (if you really want to on a multiple choice test) and gives us the same answer of 52 when we let n=1 and k=100.
F(n+k) = F(n) + k/2,
you can get
F(0+k) = 3/2 + k/2 =(k+3)/2
very easily if you merely solve for F(0) from the original function.
I wrote out some terms in the series and guessed. Some of the comments above outline another approach to derive the formula.
Post a Comment