BMO2 2001 Question 1 Recurrence Relation Ahmed and Beth have respectively $p$ and $q$ marbles, with
$p > q$. Starting with Ahmed, each in turn gives to the other as many
marbles as the other already possesses. It is found that after
$2n$ such transfers, Ahmed has $q$ marbles and Beth has $p$
marbles. Find $\frac{p}{q}$ in terms of $n$.
The number of marbles each person has seems to follow a pattern, for example: Ahmed initially has $p$ marbles then $p-q$ and then $2p-2q$, with the coefficient of $p$ initially $1$ and the coefficient of $q$ initially $0$, they follow the pattern that $a_{m+1}=2a_{m}$ if $m$ is odd and $a_{m+1}=2a_{m}-1$ if $m$ is even (where $m$ is the number of exchanges), a similar result is true for Beth. I though if I could find a formula for $a_{m}$ in terms of $n$ the I could set it equal to $q$ in Ahmed's case and find $\frac{p}{q}$ in terms of $n$, but I can't find of way of doing this. I've also considered trig substitution, but I don't really know what to substitute. 
If anyone could come up with an answer, that would be greatly appreciated.
 A: You already have a good answer, this is just another way to solve the recurrence.  Let $p+q = S$ and denote $a(n)$ the marbles Ahmed has. Clearly $a(0) = p$.
So let $a(2k)$ denote the marbles Ahmed has after $2k$ transfers.  Then Beth must have $S-a(2k)$ marbles by the Law of Conservation of Marbles.  next transfer must then lead to $a(2k+1) = a(2k)-(S-a(2k))= 2a(2k)-S$, and after that we have $a(2k+2) = 4a(2k)-2S$.
We may now define $f(k) = a(2k)$ to simplify things, and get the recursion
$$f(k+1) = 4f(k)-2S$$
with $f(0)=p$. Solving this would give
$$f(k) = \frac13\left((4^k+2)p-2(4^k-1)q \right)$$
Setting $f(n)=q$, we have $3q = (4^k+2)p-2(4k-1)q \implies \dfrac{p}q = \dfrac{2\cdot4^n+1}{4^n+2}$...
A: One approach might be to explore for a solution.  
For example it is easy to find that for $n=1$ the solution is $\frac{p}{q}=\frac{3}{2}$ and not difficult to find that for $n=2$ the solution is $\frac{p}{q}=\frac{11}{6}$.  So you might guess that in general $p=q+1$.  This leads quite quickly to finding for $n=3$ that $\frac{p}{q}=\frac{43}{22}$ with a pattern that looks like: 
43  22
21  44
42  23
19  46
38  27
11  54
22  43

Now consider the changes after each pair for Ahmed in having $43, 42, 38, 22$, which are reductions of $1,4,16$, looking like powers of $4$, and as an geometric series they add up to $p-q = (4^n-1)/3$ which you can combine with $p=2q-1$ to give $q=(4^n+2)/3$ and $p=(2\times4^n+1)/3$ and so a ratio of $\dfrac{p}{q}=\dfrac{2\times4^n+1}{4^n+2}$ to answer the question.
You still need to prove this works.  But the only difficult part is to show that if after $k$ pairs of swaps Ahmed has  $\dfrac{2\times4^n+1}{3}  - \dfrac{4^k-1}{3}$ and Beth has $\dfrac{4^n+2}{3}  + \dfrac{4^k-1}{3}$, then after the next swap Ahmed has $\dfrac{4^n-1}{3} - 2\times \dfrac{4^k-1}{3}$ and after the following swap $\dfrac{2\times4^n-1}{3} - 4\times \dfrac{4^k-1}{3} = \dfrac{2\times4^n+1}{3} - \dfrac{4^{k+1}-1}{3}$, and so Beth has the rest, namely $\dfrac{4^n+2}{3}  + \dfrac{4^{k+1}-1}{3}$, and the proof will follow by induction.  As a further point, Ahmed's and Beth's marbles can be multiplied by a common integer without affecting the ratios.
