Let \(n\) be a positive integer. The polynomial \(\mathrm{p}\) is defined by the identity
\[\mathrm{p}(\cos\theta) \equiv \cos\big((2n+1)\theta\big) + 1\,.\]
- Show that
\[\cos\big((2n+1)\theta\big) = \sum_{r=0}^{n} \binom{2n+1}{2r} \cos^{2n+1-2r}\theta\,(\cos^2\theta - 1)^r\,.\]
- By considering the expansion of \((1+t)^{2n+1}\) for suitable values of \(t\), show that the coefficient of \(x^{2n+1}\) in the polynomial \(\mathrm{p}(x)\) is \(2^{2n}\).
- Show that the coefficient of \(x^{2n-1}\) in the polynomial \(\mathrm{p}(x)\) is \(-(2n+1)2^{2n-2}\).
- It is given that there exists a polynomial \(\mathrm{q}\) such that
\[\mathrm{p}(x) = (x+1)\,[\mathrm{q}(x)]^2\]
and the coefficient of \(x^n\) in \(\mathrm{q}(x)\) is greater than \(0\).
Write down the coefficient of \(x^n\) in the polynomial \(\mathrm{q}(x)\) and, for \(n \geqslant 2\), show that the coefficient of \(x^{n-2}\) in the polynomial \(\mathrm{q}(x)\) is
\[2^{n-2}(1-n)\,.\]
- By considering the binomial expansion of \((1+x)^{2m+1}\), prove that
\[
\binom{ 2m \! +\! 1}{ m} < 2^{2m}\,,
\]
for any positive integer \(m\).
- For any positive integers \(r\) and \(s\) with \(r< s\), \(P_{r,s}\) is defined as follows: \(P_{r,s}\) is the product of all the prime numbers greater than \(r\) and less than or equal to \(s\), if there are any such primes numbers; if there are no such primes numbers, then \(P_{r,s}=1\,\).
For example, \(P_{3,7}=35\), \(P_{7,10}=1\) and \(P_{14,18}=17\).
Show that, for any positive integer \(m\),
\(P_{m+1\,,\, 2m+1} \) divides \(\displaystyle \binom{ 2m \! +\! 1}{ m} \,,\) and deduce that
\[
P_{m+1\,,\, 2m+1} < 2^{2m}
\,.
\]
- Show that, if \(P_{1,k} < 4^k\) for \(k = 2\), \(3\), \(\ldots\), \(2m\),
then \( P_{1,2m+1} < 4^{2m+1}\,\).
- Prove that \(\P_{1,n} < 4^n\) for \(n\ge2\).
Show Solution
- Notice that \((1+x)^{2m+1} = 1+\binom{2m+1}{1}x+\cdots + \binom{2m+1}{m}x^{m} + \binom{2m+1}{m+1} + \cdots\). Notice also that \(\binom{2m+1}{m} = \binom{2m+1}{m+1}\). Therefore evaluating at \(x = 1\), we see \(2^{2m+1} > \binom{2m+1}{m} + \binom{2m+1}{m+1} = 2 \binom{2m+1}{m} \Rightarrow \binom{2m+1}{m} < 2^{2m}\)
- Each prime dividing \(P_{m+1, 2m+1}\) divides the numerator of \(\binom{2m+1}{m}\) since it appears in \((2m+1)!\), but not the denominator, since they wont appear in \(m!\) or \((m+1)!\), and since they are prime they have to appear to divide it. Therefore the must divide \(\binom{2m+1}{m}\) and therefore \(P_{m+1,2m+1}\) must divide that binomail coefficient. Since \(a \mid b \Rightarrow a \leq b\) we must have \(P_{m+1, 2m+1} \leq \binom{2m+1}{m} < 2^{2m}\)
- Since
\begin{align*}
P_{1,2m+1} &= P_{1,m+1}P_{m+1, 2m+1} \tag{split into primes below \(m+1\) and abvoe} \\
&< 4^{m+1}P_{m+1,2m+1} \tag{use the condition from the question}\\
&<4^{m+1}2^{2m} \tag{use our inequality} \\
&= 4^{2m+1}
\end{align*}
- We proceed by (strong) induction.
Base case: (\(n = 2\)): \(P_{1,2} = 2 < 4^2 =16\)
Suppose it is true for all \(k=2,3,\cdots,2m\) then it is true for \(k=2m+1\) by the previous part of the question. However it is also true for \(k=2m+2\), since that can never be prime (as n is now an even number bigger than 2).
Therefore by the principle of mathematical induction it is true for all \(n\).
For positive integers \(n\), \(a\) and \(b\), the integer \(c_r\) (\(0\le r\le n\)) is defined to be the coefficient of \(x^r\) in the expansion in powers of \(x\) of \((a+bx)^n\). Write down an expression for \(c_r\) in terms of \(r\), \(n\), \(a\) and \(b\). For given \(n\), \(a\) and \(b\), let \(m\) denote a value of \(r\) for which \(c_r\) is greatest (that is, \(c_m \ge c_r\) for \(0\le r\le n\)).
Show that
\[
\frac{b(n+1)}{a+b} - 1 \le m \le \frac {b(n+1)}{a+b} \,.
\]
Deduce that \(m\) is either a unique integer or one of
two consecutive integers. Let \(G(n,a,b)\) denote the unique value of \(m\) (if there is one) or the larger of the two possible values of \(m\).
- Evaluate \(G(9,1,3)\) and \(G(9,2,3)\).
- For any positive integer \(k\), find \(G(2k,a,a)\) and \(G(2k-1,a,a)\) in terms of \(k\).
- For fixed \(n\) and \(b\), determine a value of \(a\) for which \(G(n,a,b)\) is greatest.
- For fixed \(n\), find the greatest possible value of \(G(n,1,b)\). For which values of \(b\) is this greatest value achieved?
Show Solution
\(c_r = \binom{n}{r}a^{n-r}b^r\)
\begin{align*}
&& c_m &\geq c_{m+1} \\
\Rightarrow && \binom{n}{m} a^{n-m}b^m &\geq \binom{n}{m+1} a^{n-m-1}b^{m+1} \\
\Rightarrow && \frac{1}{(n-m)}a &\geq \frac{1}{m+1}b \\
\Rightarrow && (m+1)a &\geq (n-m)b \\
\Rightarrow && m(a+b) &\geq nb -a \\
\Rightarrow && m &\geq \frac{n(b+1)-a-b}{a+b}=\frac{n(b+1)}{a+b} - 1 \\
\\
&& c_m &\geq c_{m-1} \\
\Rightarrow && \binom{n}{m} a^{n-m}b^m &\geq \binom{n}{m-1} a^{n-m+1}b^{m-1} \\
\Rightarrow && \frac{1}m b &\geq \frac{a}{(n-m+1)} \\
\Rightarrow && (n-m+1)b &\geq ma \\
\Rightarrow && (n+1)b &\geq m(a+b) \\
\Rightarrow && m &\leq \frac{(n+1)b}{a+b}
\end{align*}
Since \(m\) lies between two values \(1\) apart is is either equal to one of those two values or is the unique integer between them.
Let \(\displaystyle G(n,a,b) = \left \lfloor \frac{b(n+1)}{a+b} \right \rfloor\), so
- \(\,\) \begin{align*}
&& G(9,1,3) &= \left \lfloor \frac{3(9+1)}{1+3} \right \rfloor \\
&&&= \left \lfloor \frac{30}{4} \right \rfloor \\
&&&= 7 \\
\\
&& G(9,2,3) &= \left \lfloor \frac{3(9+1)}{2+3} \right \rfloor \\
&&&= \left \lfloor \frac{30}{5} \right \rfloor \\
&&&= 6
\end{align*}
- \(\,\) \begin{align*}
&& G(2k, a, a) &= \left \lfloor \frac{a(2k+1)}{a+a} \right \rfloor \\
&& &= \left \lfloor \frac{2k+1}{2} \right \rfloor \\
&&&= k \\
\\
&& G(2k-1, a, a) &= \left \lfloor \frac{a(2k-1+1)}{a+a} \right \rfloor \\
&& &= \left \lfloor k\right \rfloor \\
&&&= k \\
\end{align*}
- \(G(n,a,b)\) is decreasing in \(a\), therefore take \(a = 1\).
- For fixed \(n\), we are looking at \(\frac{a(n+1)}{a+b}\) and we want this to be as large as possible. By considering \((n+1) - \frac{b(n+1)}{a+b}\) we can see this is increasing in \(b\) and the largest value possible is \(n\). This is achieved when
\begin{align*}
&& \frac{b(n+1)}{a+b} & \geq n \\
\Leftrightarrow && bn + b &\geq na + bn \\
\Leftrightarrow && b& \geq na
\end{align*}
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\)?
Show 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}\)
By considering the expansion
of \(\left(1+x\right)^{n}\) where \(n\) is a positive integer,
or otherwise, show that:
- \[\binom{n}{0}+\binom{n}1+\binom{n}2 +\cdots +\binom{n}n=2^{n} \]
- \[\binom{n}{1}+2\binom{n}2+3\binom{n}3 +\cdots +n\binom{n}n=n2^{n-1} \]
- \[\binom{n}{0}+\frac12\binom{n}1+\frac13\binom{n}2 +\cdots +\frac1{n+1}\binom{n}n=\frac1{n+1}(2^{n+1}-1) \]
- \[\binom{n}{1}+2^2\binom{n}2+3^2\binom{n}3 +\cdots +n^2\binom{n}n=n(n+1)2^{n-2} \]
Show Solution
- Notice that
\begin{align*}
&& (1+x)^n &= \sum_{i=0}^n \binom{n}{i} x^i \\
\text{Evaluate at }x = 1: && 2^n &= \sum_{i=0}^n \binom{n}{i}
\end{align*}
- \(\,\)
\begin{align*}
&& (1+x)^n &= \sum_{i=0}^n \binom{n}{i} x^i \\
\frac{\d}{\d x}: && n(1+x)^{n-1} &= \sum_{i=1}^n i\binom{n}{i} x^{i-1} \\
\text{Evaluate at }x = 1: && n2^{n-1} &= \sum_{i=1}^n i\binom{n}{i}
\end{align*}
- \(\,\)
\begin{align*}
&& (1+x)^n &= \sum_{i=0}^n \binom{n}{i} x^i \\
\Rightarrow && \int_0^1(1+x)^n \d x &= \int_0^1 \sum_{i=0}^n \binom{n}{i} x^i \d x \\
\Rightarrow && \frac{1}{n+1}(2^{n+1}-1) &= \sum_{i=0}^n \binom{n}{i}\int_0^1 x^i \d x\\
&&& = \sum_{i=0}^n \frac{1}{i+1}\binom{n}{i} \\
\end{align*}
- \(\,\)
\begin{align*}
&& (1+x)^n &= \sum_{i=0}^n \binom{n}{i} x^i \\
\frac{\d}{\d x}: && n(1+x)^{n-1} &= \sum_{i=1}^n i\binom{n}{i} x^{i-1} \\
\times x: && nx(1+x)^{n-1} &= \sum_{i=1}^n i\binom{n}{i} x^{i} \\
\frac{\d}{\d x}: && n(1+x)^{n-1}+n(n-1)x(1+x)^{n-2} &= \sum_{i=1}^n i^2\binom{n}{i} x^{i-1} \\
\text{Evaluate at }x = 1: && \sum_{i=1}^n i^2\binom{n}{i} &= n(1+1)^{n-1}+n(n-1)x(1+1)^{n-2} \\
&&&= 2^{n-2} \left (n(n-1) + 2n \right) \\
&&&= n(n+1)2^{n-2}
\end{align*}
Show that the coefficient of \(x^{-12}\) in the expansion of
\[
\left(x^{4}-\frac{1}{x^{2}}\right)^{5}
\left(x-\frac{1}{x}\right)^{6}
\]
is \(-15\), and calculate the coefficient of \(x^2\).
Hence, or otherwise,
calculate the coefficients of \(x^4\) and \(x^{38}\) in the expansion of
\[
(x^2-1)^{11}(x^4+x^2+1)^5.
\]
Show Solution
The powers of \(x\) in the first bracket will be \(x^{20}, x^{14}, \cdots, x^{-10}\). The powers of \(x\) in the second bracket will be \(x^6, x^4, \cdots, x^{-6}\).
Therefore we can achieve \(x^{-12}\) in only one way:
\begin{array}{c|c|c|c|c}
1\text{st bracket} & 2\text{nd bracket} & 1\text{st coef} & 2\text{nd coef} & \text{prod} \\ \hline
x^{-10} & x^{-2} & \binom{5}{5}(-1)^5 = -1 & \binom{6}{4}(-1)^4 = 15& -15 \\
\end{array}
We can achieve \(x^2\) as follows:
\begin{array}{c|c|c|c|c}
1\text{st bracket} & 2\text{nd bracket} & 1\text{st coef} & 2\text{nd coef} & \text{prod} \\ \hline
x^{-4} & x^{6} & \binom{5}{4}(-1)^4 = 5 & \binom{6}{0}(-1)^0 = 1& 5 \\
x^{2} & x^{0} & \binom{5}{3}(-1)^3 = -10 & \binom{6}{3}(-1)^3 = -20 & 200 \\
x^{8} & x^{-6} & \binom{5}{2}(-1)^2 = 10 & \binom{6}{6}(-1)^6 = 1 & 10
\end{array}
Therefore the coefficient is \(215\)
\((x^2-1)(x^4+x^2+1) = x^6-1\), therefore
\begin{align*}
(x^2-1)^{11}(x^4+x^2+1)^5 &= (x^2-1)^6(x^6-1)^5 \\
&= x^6\left(x-\frac1x\right)^6(x^6-1)^6 \\
&= x^6\left(x-\frac1x\right)^6\left(x^2\left(x^4-\frac{1}{x^2}\right)\right)^5 \\
&= x^6\left(x-\frac1x\right)^6x^{10}\left(x^4-\frac{1}{x^2}\right)^5 \\
&= x^{16}\left(x-\frac1x\right)^6\left(x^4-\frac{1}{x^2}\right)^6 \\
\end{align*}
Therefore the coefficient of \(x^4\) is the coefficient of \(x^{4-16} = x^{-12}\) in our original expression, ie \(-15\).
Similarly, the coefficient of \(x^{38}\) is the coefficient of \(x^{38-16} = x^{22}\), which can only be achieved in one way:
\begin{array}{c|c|c|c|c}
1\text{st bracket} & 2\text{nd bracket} & 1\text{st coef} & 2\text{nd coef} & \text{prod} \\ \hline
x^{20} & x^{2} & \binom{5}{0}(-1)^0 = 1 & \binom{6}{2}(-1)^2 = 15& 15 \\
\end{array}
Therefore the coefficient is \(15\)
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:
- 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};\)
- \(\displaystyle \sum\limits_{t=1}^ n 2t { n \choose t}^2 = n {2n\choose n} .\)
Show 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\)
- 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\)
- 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}\)
By considering the coefficient of \(x^{n}\) in the identity \((1-x)^{n}(1+x)^{n}=(1-x^{2})^{n},\) or otherwise, simplify
\[
\binom{n}{0}^{2}-\binom{n}{1}^{2}+\binom{n}{2}^{2}-\binom{n}{3}^{2}+\cdots+(-1)^{n}\binom{n}{n}^{2}
\]
in the cases (i) when \(n\) is even, (ii) when \(n\)
is odd.
Show Solution
The coefficient of \(x^n\) on the LHS is
\begin{align*}
&& (1-x^2)^n &= (1-x)^n(1+x)^n \\
[x^n]: && \begin{cases} (-1)^{\lfloor \frac{n}2 \rfloor}\binom{n}{\lfloor \frac{n}2 \rfloor} &\text{if } n\text{ even} \\
0 & \text{otherwise}
\end{cases} &= \sum_{i=0}^n \underbrace{(-1)^i\binom{n}{i}}_{\text{take }(-x)^i\text{ from first bracket}} \cdot \underbrace{\binom{n}{n-i}}_{\text{take }x^{n-i}\text{ from second bracket}} \\
&&&= \sum_{i=0}^n (-1)^i\binom{n}{i}\binom{n}{i} \\
&&&= \sum_{i=0}^n (-1)^i\binom{n}{i}^2\\
\end{align*}
Write down the binomial expansion of \((1+x)^{n}\), where \(n\) is a
positive integer.
- By substituting particular values of \(x\) in the above expression, or otherwise, show that, if \(n\) is an even positive integer,
\[
\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{n}=\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\cdots+\binom{n}{n-1}=2^{n-1}.
\]
- Show that, if \(n\) is any positive integer, then
\[
\binom{n}{1}+2\binom{n}{2}+3\binom{n}{3}+\cdots+n\binom{n}{n}=n2^{n-1}.
\]
Hence evaluate
\[
\sum_{r=0}^{n}\left(r+(-1)^{r}\right)\binom{n}{r}\,.
\]
Show Solution
\[ (1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k \]
- \begin{align*}
(1+1)^n &= \sum_{k=0}^n \binom{n}{k} \\
(1-1)^n &= \sum_{k=0}^n (-1)^n\binom{n}{k} \\
&= \sum_{\text{even }k, 0 \leq k \leq n} \binom{n}{k} -\sum_{\text{odd }k, 0 \leq k \leq n} \binom{n}{k}
\end{align*}
Therefore \(\displaystyle \sum_{\text{even }k, 0 \leq k \leq n} \binom{n}{k} = \sum_{\text{odd }k, 0 \leq k \leq n} \binom{n}{k} = \frac{2^n}{2} = 2^{n-1}\)
- \begin{align*}
&& (1+x)^n &= \sum_{k=0}^n \binom{n}{k}x^k \\
\frac{\d}{\d x}: && n(1+x)^{n-1} &= \sum_{k=0}^n k\binom{n}{k} x^{k-1} \\
x = 1: && n2^{n-1} &= \sum_{k=1}^n k\binom{n}{k}
\end{align*} as required
\begin{align*}
\sum_{r=0}^n (r + (-1)^r) \binom{n}{r} &= n2^{n-1}+0 = n2^{n-1}
\end{align*}