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.
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.
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.
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.
Post a Comment