STEP II/III 2014 solutions

Hi, anyone want help, feel free to PM me

Posted from TSR Mobile

Help with what? Feeding trolls?

Shouldn't the last statement be
$\text{G}(n,1,b)_{\text{max}}=n \text{ for } b \geq n$

Can you, or anyone else, explain the last part of (iv) more clearly please?

You have E(Y) expressible in two ways; the standard and the bit proved in the question. Thus these two different expressions for the expectation are equal and thus their difference is 0 i.e.:

$\displaystyle\sum_{0}^{n} xP(X=x) - \displaystyle\sum_{1}^{n} P(Y\geq k ) = 0$

You have expressions for E(X) in both of these two forms (I probably should've written the full sum in for ii) instead of the standard formula) so it is then plugging in and re-arranging to get the expression required.

I just can't fathom where the squares come from, i.e. m[text]\frac{2^2}{n}, \frac{3^2}{n}

The expression for P(X=r) has a r/n factor; when you do $E[X] = \sum r P(X = r)$ you're going to end up with a r^2 / n term.

But $(1-\frac{r}{n})\frac{r}{n} \neq (1-\frac{r^2}{n})$ ??
Can you explain it in a form that would be acceptable in the examination?

II/12:

(i)



(ii)



(iii)



(iv)



(v)

In the final answer for part (v), shouldn't the $\frac{t}{\theta} \text{ term be to the power } \lambda-1$ ?

OK, once I actually started doing the calculations, I realised what I'd written before had an off-by-one error, which means there's a little bit of fiddling to get the final expression.

If X>=r then the first r-1 numbers are distinct (probability = (1 - 1/n)(1-2/n)...(1-(r-2)/n)),
So $P(X\ge r) = (1 - \frac{1}{n})(1-\frac{2}{n})...(1-\frac{r-2}{n})$

If X = r, then in addition the rth number matches one of the first (r-1) (probability = (r-1) / n).
So $P(X=r) = (1 - \frac{1}{n})(1-\frac{2}{n})...(1-\frac{r-2}{n})\frac{r-1}{n}$ (also $P(X=r) = P(X \ge r) \frac{r-1}{n}$

I'll skip showing $E(X) = \sum_1^N P(X\ge k)$. But given that, we must have

$\sum_1^N P(X \ge k) - \sum_1^N k P(X = k) = 0$. Now our other formulae above all require k >=2 (k=1 has probability 0), so rewrite this as $1 + \sum_2^N P(X \ge k) - \sum_2^N k P(X=k) = 0$. But we also showed $P(X=k) = \frac{k-1}{n} P(X\ge k)$, so

$P(X \ge k) - kP(X=k) = P(X\ge k) - P(X \ge k) \frac{k(k-1)}{n}$

$= P(X\ge k)(1-\frac{k(k-1)}{n})$

So we must have (all sums from this point start with k =2):

$0 = 1 + \sum P(X \ge k) (1 - \frac{k(k-1)}{n})$. The sum is almost what we want, but not quite. So we'll rewrite k(k-1) as (k-1)^2 + (k-1):

$0 = 1 + \sum P(X \ge k)(1-\frac{(k-1)^2 + (k-1)}{n})$

$0 = 1 + \sum P(X \ge k)(1-\frac{(k-1)^2}{n}) - \sum P(X \ge k) \frac{k-1}{n}$.

Now use $P(X=k) = \frac{k-1}{n} P(X\ge k)$ again to replace the sum on the RHS by $\sum P(X = k)$ which of course sums to 1.

So we are left with $\sum P(X \ge k)(1-\frac{(k-1)^2}{n})= 0$ which is the desired result after subbing back our expression for P(X >= k).

[This is very similar to the solution already posted, so I'm not sure how much help this is!

The one observation I'll make is that the $(1-\frac{r^2}{n^2})$ term doesn't come by multiplying $(1-\frac{r}{n})$, it comes from multiplying $\frac{r}{n}$ by (r+1), fiddling to get $\frac{r^2}{n^2} + \frac{r}{n}$ and then subtracting the r^2/n^2 part from 1.]

Yes. I wrote \lamda rather than \lambda in the LaTeX

There is an error in your solution to the second DE. Capital omega = 3 ... Not 2 ...

Your explanation as to why Y doesn't return to initial point is very flimsy. You are right but don't explain fully. If both cos terms are equal to 1 then one must be 2mPI and the other 2nPI when with a little manipulation you come out with the contradiction that root 3 must be rational.

Step III Question 10

At end:-

So for Y to return to its original position we must have both cosines equal to 1 which can never happen except at t=0

This is a statement not a proof....I think you need to show why this is impossible!!

STEP III, Q8:

For any 2 positive integers M < N, we have f(M) > f(M+1) > ... > f(N). The sum has (N+1-M) terms, all terms are >= f(N), and N-M terms are > f(N). So $\sum_{n=M}^N f(n) > \sum_{n=M}^N f(N) = (N+1-M) f(N)$ and similarly $\sum_M^N f(n) < (M+1-N) f(M)[$.

Put $M = k^n, N = k^{n+1} - 1$. $(N+1-M) = k^n(k-1)$, so as long as k >2 or n > 0 we have N+1-M > 1. (We can't prove strict inequality in the case n=0, k=2, but if you plug these in, we do actually get equality on the RHS, so it's not actually a strict inequality in this case, which is a minor error in the question).

But assuming we do have (N+1-M) > 1, then M < N, and so by the above we have $k^n(k-1)f(k^{n+1}) < \sum_{r=k^n}^{k^{n+1}-1} f(r) < k^n(k-1)f(k^n)$ as desired.

(i) Let f(n) = 1/n and k =2. Then we have $\displaystyle 2^n \dfrac{1}{2^{n+1}} < \sum_{r=2^n}^{2^{n+1}-1} \frac{1}{r} < 2^n \dfrac{1}{2^n}$, so $\displaystyle \dfrac{1}{2} < \sum_{r=2^n}^{2^{n+1}-1} \frac{1}{r} < 1$.

This gives us:

$\displaystyle \sum_{n=0}^N \dfrac{1}{2} <\sum_{n=0}^N \sum_{r=2^n}^{2^{n+1}-1} \frac{1}{r} < \sum_{n=0}^N 1$ and so $\displaystyle \frac{N+1}{2} < \sum_1^{2^{N+1}-1} \frac{1}{r} < N+1$ as desired.(note that again we actually get equality when N = 0).

(ii) Now take f(n) = 1/n^3, k = 2. We get $\sum_{r=2^n}^{2^{n+1}-1} \frac{1}{r^3} < 2^n \dfrac{1}{2^{3n}} = 1/4^n$ and so

$\sum_{n=0}^N \sum_{r=2^n}^{2^{n+1}-1} \frac{1}{r^3} < \sum_{n=0}^N 1/4^n$ so $\sum_{r=1}^{2^{N+1}-1} \frac{1}{r^3} < \sum_0^N (1/4)^n < \sum_0^\infty (1/4)^n = 4/3$ and so finally $\sum_{r=1}^\infty \frac{1}{r^3} < 4/3$.

(iii) Assume we write all integers 0, 1, ..., 999 using leading zeros (e.g. "009" for 9). Then $S(1000) \cup \{0\}$ is the set of all numbers where all 3 digits are NOT equal to 2. So there are 9 choices for each digit, so a total of 9^3 possibilities. Removing the "000" case (since 0 is not a positive integer) leaves 9^3 -1 as required.

Now for k>0 $\rho(10^{k})-\rho(10^{k-1})$ is the sum of the reciprocals of all k digit numbers without a 2. There are 8 choices for the leading digit, 9 choices for each of the other k-1 digits, so there are $8 \cdot 9^{k-1}$ numbers of this form, and each number is at least $10^{k-1}$ (and at least one is larger). So $\rho(10^{k})-\rho(10^{k-1}) < 8\cdot 9^{k-1}/(10^{k-1}) = 8\left(\frac{9}{10}\right)^{k-1}$.

So $\rho(10^k) < 8 \sum_1^k \left(\frac{9}{10}\right)^{k-1} < 8 \frac{1}{1-9/10} = 80$. Since $\rho(10^k) \geq \rho(n)$ whenever 10^k > n, the result follows.

Note: I thought it more intuitive to do the end this way - it's probably not what they wanted, but it's essentially the same underneath. Also this was LaTeX hell, so there may well be typos.

In the first part you have the lower limit for the sum to be $(N+1-M)\mathbf{f}(N)$
but when you substitute $N=k^{n+1}-1$ you have $\mathbf{f}(k^{n+1})$ What happened to the -1?

If f is decreasing, f(k^(n+1)) < f^(k^(n+1) - 1).

(i.e. I wrote:

$k^n(k-1)f(k^{n+1}) < \sum_{r=k^n}^{k^{n+1}-1} f(r)$

but if you want every step it's:

$k^n(k-1)f(k^{n+1}) < k^n(k-1)f(k^{n+1}-1) \sum_{r=k^n}^{k^{n+1}-1} f(r)$

STEP III, Q8:

For any 2 positive integers M < N, we have f(M) > f(M+1) > ... > f(N). The sum has (N+1-M) terms, all terms are >= f(N), and N-M terms are > f(N). So $\sum_{n=M}^N f(n) > \sum_{n=M}^N f(N) = (N+1-M) f(N)$ and similarly $\sum_M^N f(n) < (M+1-N) f(M)[$.

Put $M = k^n, N = k^{n+1} - 1$. $(N+1-M) = k^n(k-1)$, so as long as k >2 or n > 0 we have N+1-M > 1. (We can't prove strict inequality in the case n=0, k=2, but if you plug these in, we do actually get equality on the RHS, so it's not actually a strict inequality in this case, which is a minor error in the question).

But assuming we do have (N+1-M) > 1, then M < N, and so by the above we have $k^n(k-1)f(k^{n+1}) < \sum_{r=k^n}^{k^{n+1}-1} f(r) < k^n(k-1)f(k^n)$ as desired.

(i) Let f(n) = 1/n and k =2. Then we have $\displaystyle 2^n \dfrac{1}{2^{n+1}} < \sum_{r=2^n}^{2^{n+1}-1} \frac{1}{r} < 2^n \dfrac{1}{2^n}$, so $\displaystyle \dfrac{1}{2} < \sum_{r=2^n}^{2^{n+1}-1} \frac{1}{r} < 1$.

This gives us:

$\displaystyle \sum_{n=0}^N \dfrac{1}{2} <\sum_{n=0}^N \sum_{r=2^n}^{2^{n+1}-1} \frac{1}{r} < \sum_{n=0}^N 1$ and so $\displaystyle \frac{N+1}{2} < \sum_1^{2^{N+1}-1} \frac{1}{r} < N+1$ as desired.(note that again we actually get equality when N = 0).

(ii) Now take f(n) = 1/n^3, k = 2. We get $\sum_{r=2^n}^{2^{n+1}-1} \frac{1}{r^3} < 2^n \dfrac{1}{2^{3n}} = 1/4^n$ and so

$\sum_{n=0}^N \sum_{r=2^n}^{2^{n+1}-1} \frac{1}{r^3} < \sum_{n=0}^N 1/4^n$ so $\sum_{r=1}^{2^{N+1}-1} \frac{1}{r^3} < \sum_0^N (1/4)^n < \sum_0^\infty (1/4)^n = 4/3$ and so finally $\sum_{r=1}^\infty \frac{1}{r^3} < 4/3$.

(iii) Assume we write all integers 0, 1, ..., 999 using leading zeros (e.g. "009" for 9). Then $S(1000) \cup \{0\}$ is the set of all numbers where all 3 digits are NOT equal to 2. So there are 9 choices for each digit, so a total of 9^3 possibilities. Removing the "000" case (since 0 is not a positive integer) leaves 9^3 -1 as required.

Now for k>0 $\rho(10^{k})-\rho(10^{k-1})$ is the sum of the reciprocals of all k digit numbers without a 2. There are 8 choices for the leading digit, 9 choices for each of the other k-1 digits, so there are $8 \cdot 9^{k-1}$ numbers of this form, and each number is at least $10^{k-1}$ (and at least one is larger). So $\rho(10^{k})-\rho(10^{k-1}) < 8\cdot 9^{k-1}/(10^{k-1}) = 8\left(\frac{9}{10}\right)^{k-1}$.

So $\rho(10^k) < 8 \sum_1^k \left(\frac{9}{10}\right)^{k-1} < 8 \frac{1}{1-9/10} = 80$. Since $\rho(10^k) \geq \rho(n)$ whenever 10^k > n, the result follows.

Note: I thought it more intuitive to do the end this way - it's probably not what they wanted, but it's essentially the same underneath. Also this was LaTeX hell, so there may well be typos.