1 problem found
By considering the coefficient of \(x^r\) in the series for \((1+x)(1+x)^n\), or otherwise, obtain the following relation between binomial coefficients: \[ \binom n r + \binom n {r-1} = \binom {n+1} r \qquad (1\le r\le n). \] The sequence of numbers \(B_0\), \(B_1\), \(B_2\), \(\ldots\) is defined by \[ B_{2m} = \sum_{j=0}^m \binom{2m-j}j \text{ and } B_{2m+1} = \sum_{k=0}^m \binom{2m+1-k}k . \] Show that \(B_{n+2} - B_{n+1} = B_{n}\,\) (\(n=0\), \(1\), \(2\), \(\ldots\,\)). What is the relation between the sequence \(B_0\), \(B_1\), \(B_2\), \(\ldots\) and the Fibonacci sequence \(F_0\), \(F_1\), \(F_2\), \(\ldots\) defined by \(F_0=0\), \(F_1=1\) and \(F_n = F_{n-1}+F_{n-2}\) for \(n\ge2\)?
Solution: The coefficient of \(x^{r-1}\) in \((1+x)^n\) is \(\binom{n}{r-1}\) and the coefficient of \(x^r\) in \((1+x)^n\) is \(\binom{n}{r}\). The only ways to get \(x^r\) in the expansion of \((1+x)(1+x)^n\) is to either multiply the \(x^r\) term from the second expansion by \(1\) or the \(x^{r-1}\) term by \(x\). This is \(\binom{n}{r-1} + \binom{n}{r}\). However, the coefficient of \(x^r\) in \((1+x)^{n+1}\) is \(\binom{n+1}r\), so \(\binom{n}{r} + \binom{n}{n-1} = \binom{n+1}r\). Claim: \(B_{n+2} - B_{n+1} = B_{n}\). Proof: Consider \(n\) even, ie \(n = 2m\) \begin{align*} B_{n+2} - B_{n+1} &= \sum_{j=0}^{m+1} \binom{2(m+1)-j}{j} - \sum_{j=0}^m \binom{2m+1-j}{j} \\ &= \binom{2(m+1)-(m+1)}{m+1} +\sum_{j=0}^m \left ( \binom{2(m+1)-j}{j} - \binom{2m+1-j}{j} \right) \\ &= 1 + \sum_{j=1}^m \binom{2m+1-j}{j-1} \\ &= 1 + \sum_{j=0}^{m-1} \binom{2m-j}{j} \\ &= \binom{m}{m} + \sum_{j=0}^{m-1} \binom{2m-j}{j} \\ &= \sum_{j=0}^{m} \binom{2m-j}{j} \\ &= B_n \end{align*} Consider \(n\) even, ie \(n = 2m+1\) \begin{align*} B_{n+2} - B_{n+1} &= \sum_{j=0}^{m+1} \binom{2(m+1)+1-j}{j} - \sum_{j=0}^{m+1} \binom{2(m+1)-j}{j} \\ &= \sum_{j=0}^{m+1} \left (\binom{2(m+1)+1-j}{j} - \binom{2(m+1)-j}{j}\right)\\ &= \sum_{j=1}^{m+1} \binom{2(m+1)-j}{j-1} \\ &= \sum_{j=0}^{m} \binom{2m+1-j}{j} \\ &= B_n \end{align*} as required. \(B_0 = 1, B_1 = 2\), therefore \(B_n = F_{n+2}\)