Problems

Given an infinite sequence of numbers \(u_0\), \(u_1\), \(u_2\), \(\ldots\,\), we define the generating function, \(\f\), for the sequence by \[ \f(x) = u_0 + u_1x +u_2 x^2 +u_3 x^3 + \cdots \,. \] Issues of convergence can be ignored in this question.

1. Using the binomial series, show that the sequence given by \(u_n=n\,\) has generating function \(x(1-x)^{-2}\), and find the sequence that has generating function \(x(1-x)^{-3}\). Hence, or otherwise, find the generating function for the sequence \(u_n =n^2\). You should simplify your answer.
2. • \(\bf (a)\) The sequence \(u_0\), \(u_1\), \(u_2\), \(\ldots\,\) is determined by \(u_{n} = ku_{n-1}\) (\(n\ge1\)), where \(k\) is independent of \(n\), and \(u_0=a\). By summing the identity \(u_{n}x^n \equiv ku_{n-1}x^n\), or otherwise, show that the generating function, f, satisfies \[ \f(x) = a + kx \f(x) \] Write down an expression for \(\f(x)\).
   • \(\bf (b)\) The sequence \(u_0, u_1, u_2, \ldots\,\) is determined by \(u_{n} = u_{n-1}+ u_{n-2}\) (\(n\ge2\)) and \(u_0=0\), \(u_1=1\). Obtain the generating function.

Write down the general term in the expansion in powers of \(x\) of \((1-x^6)^{-2}\,\).

1. Find the coefficient of \(x^{24}\) in the expansion in powers of \(x\) of \[ (1-x^6)^{-2} (1-x^3)^{-1}\,.\] Obtain also, and simplify, formulae for the coefficient of \(x^n\) in the different cases that arise.
2. Show that the coefficient of \(x^{24}\) in the expansion in powers of \(x\) of \[ (1-x^6)^{-2} (1-x^3)^{-1} (1-x)^{-1}\,\] is \(55\), and find the coefficients of \(x^{25}\) and \(x^{66}\).

1. The coefficients in the series \[ S= \tfrac13 x + \tfrac 16 x^2 + \tfrac1{12} x^3 + \cdots + a_rx^r + \cdots \] satisfy a recurrence relation of the form \(a_{r+1} + p a_r =0\). Write down the value of \(p\). By considering \((1+px)S\), find an expression for the sum to infinity of \(S\) (assuming that it exists). Find also an expression for the sum of the first \(n+1\) terms of \(S\).
2. The coefficients in the series \[ T=2 + 8x +18x^2+37 x^3 +\cdots + a_rx^r + \cdots \] satisfy a recurrence relation of the form \(a_{r+2}+pa_{r+1} +qa_r=0\). Find an expression for the sum to infinity of \(T\) (assuming that it exists). By expressing \(T\) in partial fractions, or otherwise, find an expression for the sum of the first \(n+1\) terms of \(T\).

In the basic version of Horizons (H1) the player has a maximum of \(n\) turns, where \(n \ge 1\). At each turn, she has a probability \(p\) of success, where \(0 < p < 1\). If her first success is at the \(r\)th turn, where \(1 \le r \le n\), she collects \(r\) pounds and then withdraws from the game. Otherwise, her winnings are nil. Show that in H1, her expected winnings are $$ p^{-1}\left[1+nq^{n+1}-(n+1)q^n\right]\quad\hbox{pounds}, $$ where \(q=1-p\). The rules of H2 are the same as those of H1, except that \(n\) is randomly selected from a Poisson distribution with parameter \(\lambda\). If \(n=0\) her winnings are nil. Otherwise she plays H1 with the selected \(n\). Show that in H2, her expected winnings are $$ {1 \over p}{\left(1-{\e^{-{\lambda}p}}\right)} -{{\lambda}q}{\e^{-{\lambda}p}} \quad\hbox{pounds}. $$

By considering the coefficients of \(t^{n}\) in the equation \[(1+t)^{n}(1+t)^{n}=(1+t)^{2n},\] or otherwise, show that \[\binom{n}{0}\binom{n}{n}+\binom{n}{1}\binom{n}{n-1}+\cdots +\binom{n}{r}\binom{n}{n-r}+\cdots+\binom{n}{n}\binom{n}{0} =\binom{2n}{n}.\] The large American city of Triposville is laid out in a square grid with equally spaced streets running east-west and avenues running north-south. My friend is staying at a hotel \(n\) avenues west and \(n\) streets north of my hotel. Both hotels are at intersections. We set out from our own hotels at the same time. We walk at the same speed, taking 1 minute to go from one intersection to the next. Every time I reach an intersection I go north with probability \(1/2\) or west with probability \(1/2\). Every time my friend reaches an intersection she goes south with probability \(1/2\) or east with probability \(1/2\). Our choices are independent of each other and of our previous decisions. Indicate by a sketch or by a brief description the set of points where we could meet. Find the probability that we meet. Suppose that I oversleep and leave my hotel \(2k\) minutes later than my friend leaves hers, where \(k\) is an integer and \(0\leqslant 2k\leqslant n\). Find the probability that we meet. Have you any comment? If \(n=1\) and I leave my hotel \(1\) minute later than my friend leaves hers, what is the probability that we meet and why?

Show Solution

---

Solution: \begin{align*} && (1+t)^{n}(1+t)^{n}&=(1+t)^{2n} \\ [t^n]: &&\sum_{k=0}^n \underbrace{\binom{n}{k}}_{t^k\text{ from left bracket}} \underbrace{\binom{n}{n-k}}_{t^{n-k}\text{ from right bracket}} &= \binom{2n}{n} \end{align*}

+ - ↺

From each point, we can get to the diagonal ahead of us, so each move only takes us one diagonal closer together. Therefore we can only meet on the diagonal. The number of routes we can meet at is \begin{align*} && R &= \sum_{k=0}^n \underbrace{\binom{n}{k}}_{\text{I go up } k}\underbrace{\binom{n}{n-k}}_{\text{she goes down }n-k} \\ &&&= \binom{2n}{n} \end{align*} Therefore the probability is \(\displaystyle \frac1{2^{2n}} \binom{2n}n\). If I leave \(2k\) minutes late, then we will be attempting meet on a diagonal which is \(2k\) closer to me. The probability this occurs is \begin{align*} && \frac{1}{2^{2n}}\sum_{j=0}^{n-k}\binom{n-k}{j}\binom{n+k}{n-j} &= \frac{1}{2^{2n}}\binom{2n}{n} \end{align*} (by considering the coefficient of \(t^n\) in \((1+t)^{n+k}(1+t)^{n-k} =(1+t)^{2n}\)) This probability is unchanged, because you can consider the two paths as one path by one random person, conditional on them meeting and the delay doesn't change anything. If \(n = 1\) and I leave late, the only way we meet is if we end up walking towards each other down the same street (not at an intersection). This means I need to walk towards the intersection she reaches after the first minute \(\frac12\) and she needs to walk towards me \(\frac12\) so we have probability \(\frac14\)

I have two dice whose faces are all painted different colours. I number the faces of one of them \(1,2,2,3,3,6\) and the other \(1,3,3,4,5,6.\) I can now throw a total of 3 in two different ways using the two number \(2\)'s on the first die once each. Show that there are seven different ways of throwing a total of 6. I now renumber the dice (again only using integers in the range 1 to 6) with the results shown in the following table \noindent