Problems

Filters
Clear Filters

2 problems found

1999 Paper 2 Q4
D: 1600.0 B: 1500.0
binomial theorem binomial coefficients Vandermonde identity algebraic identity summation combinatorial proof coefficient comparison

By considering the expansions in powers of \(x\) of both sides of the identity $$ {(1+x)^n}{(1+x)^n}\equiv{(1+x)^{2n}}, $$ show that $$ \sum_{s=0}^n {n\choose s}^2 = {2n\choose n}, $$ where \(\displaystyle {n\choose s}= \frac{n!}{s!\,(n-s)!}\). By considering similar identities, or otherwise, show also that:

  1. if \(n\) is an even integer, then \(\displaystyle \sum_{s=0}^n {{(-1)}^s}{n \choose s}^2= (-1)^{n/2}{n \choose n/2};\)
  2. \(\displaystyle \sum\limits_{t=1}^ n 2t { n \choose t}^2 = n {2n\choose n} .\)

Solution: To obtain the coefficient of \(x^n\) on the RHS we clearly have \(\displaystyle \binom{2n}n\). To obtain the coefficient of \(x^n\) on the LHS we can obtain \(x^s\) from the first bracket and \(x^{n-s}\) from the second bracket, ie \(\displaystyle \sum_{s=0}^n \binom{n}{s}\binom{n}{n-s} = \sum_{s=0}^n \binom{n}{s}\binom{n}{s} = \sum_{s=0}^n \binom{n}{s}^2\)

  1. Consider \((1-x)^n(1+x)^n = (1-x^2)^n\), then the coefficient of \(x^n\) (if \(n\) is even) is for the RHS \(\displaystyle (-1)^{n/2} \binom{n}{n/2}\). For the LHS, we can obtain \(x^n\) via \(x^s\) and \(x^{n-s}\) which is \(\displaystyle \sum_{s=0}^n (-1)^s\binom{n}{s}\binom{n}{n-s} = \sum_{s=0}^n (-1)^s\binom{n}{s}^2\)
  2. Notice that \begin{align*} && \sum_{t=1}^ n 2t { n \choose t}^2 &= n {2n\choose n} \\ \Leftrightarrow && \sum_{t=1}^ n 2t \frac{n}{t} { n-1 \choose t-1}\binom{n}{t} &= n \frac{2n}{n}{2n-1\choose n-1} \\ \Leftrightarrow && \sum_{t=1}^ n { n-1 \choose t-1}\binom{n}{t} &= {2n-1\choose n-1} \\ \Leftrightarrow && \sum_{t=1}^ n { n-1 \choose t-1}\binom{n}{n-t} &= {2n-1\choose n-1} \\ \end{align*} but this is exactly what we would obtain by considering the coefficient of \(x^{n-1}\) in \((1+x)^{n-1}(1+x)^n \equiv (1+x)^{2n-1}\)

View
1996 Paper 2 Q13
D: 1600.0 B: 1516.0
binomial distribution Vandermonde identity combinatorial proof random walk grid probability binomial coefficients generating functions

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?

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*}

TikZ diagram
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\)

View