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