Let \(\lfloor x \rfloor\) denote the largest integer that satisfies \(\lfloor x \rfloor \leq x\).
For example, if \(x = -4.2\), then \(\lfloor x \rfloor = -5\).
- Show that, if \(n\) is an integer, then \(\lfloor x + n \rfloor = \lfloor x \rfloor + n\).
- Let \(n\) be a positive integer and define function \(f_n\) by
\[f_n(x) = \lfloor x \rfloor + \left\lfloor x + \frac{1}{n} \right\rfloor + \left\lfloor x + \frac{2}{n} \right\rfloor + \ldots + \left\lfloor x + \frac{n-1}{n} \right\rfloor - \lfloor nx \rfloor\]
- Show that \(f_n\left(x + \frac{1}{n}\right) = f_n(x)\).
- Evaluate \(f_n(t)\) for \(0 \leq t < \frac{1}{n}\).
- Hence show that \(f_n(x) \equiv 0\).
- Show that \(\left\lfloor \frac{x}{2} \right\rfloor + \left\lfloor \frac{x+1}{2} \right\rfloor = \lfloor x \rfloor\).
- Hence, or otherwise, simplify
\[\left\lfloor \frac{x+1}{2} \right\rfloor + \left\lfloor \frac{x+2}{2^2} \right\rfloor + \ldots + \left\lfloor \frac{x+2^k}{2^{k+1}} \right\rfloor + \ldots\]
Show Solution
- Claim: If \(n \in \mathbb{Z}\) then \(\lfloor x + n \rfloor = \lfloor x \rfloor + n\)
Proof: Since \(\lfloor x \rfloor \leq x\) then \(\lfloor x \rfloor + n \leq x + n\) and \(\lfloor x \rfloor + n \in \mathbb{Z}\) we must have that \(\lfloor x \rfloor +n \leq \lfloor x + n \rfloor\). However, since \(\lfloor x \rfloor + 1 > x\) we must also have that \(\lfloor x \rfloor + 1 + n > x + n\), therefore \(\lfloor x \rfloor + n\) is the largest integer less than \(x + n\) as required.
- Claim: \(f_n\left(x + \frac{1}{n}\right) = f_n(x)\)
Proof:
\begin{align*}
f_n\left(x + \frac{1}{n}\right) &=\left \lfloor x+ \frac{1}{n} \right \rfloor + \left\lfloor x + \frac{1}{n}+ \frac{1}{n} \right\rfloor + \left\lfloor x+ \frac{1}{n} + \frac{2}{n} \right\rfloor + \ldots + \left\lfloor x+ \frac{1}{n} + \frac{n-1}{n} \right\rfloor - \left \lfloor n\left ( x + \frac{1}{n} \right) \right \rfloor \\
&= \left \lfloor x+ \frac{1}{n} \right \rfloor + \left\lfloor x + \frac{2}{n}\right\rfloor + \left\lfloor x+ \frac{3}{n} \right\rfloor + \ldots + \left\lfloor x+ \frac{n}{n} \right\rfloor - \left \lfloor nx + 1 \right \rfloor \\
&= \left \lfloor x+ \frac{1}{n} \right \rfloor + \left\lfloor x + \frac{2}{n}\right\rfloor + \left\lfloor x+ \frac{3}{n} \right\rfloor + \ldots + \left\lfloor x+ 1 \right\rfloor - \left \lfloor nx + 1 \right \rfloor \\
&= \left \lfloor x+ \frac{1}{n} \right \rfloor + \left\lfloor x + \frac{2}{n}\right\rfloor + \left\lfloor x+ \frac{3}{n} \right\rfloor + \ldots + \lfloor x \rfloor + 1 - \left ( \lfloor nx \rfloor + 1 \right) \\
&= \lfloor x \rfloor + \left\lfloor x + \frac{1}{n} \right\rfloor + \left\lfloor x + \frac{2}{n} \right\rfloor + \ldots + \left\lfloor x + \frac{n-1}{n} \right\rfloor - \lfloor nx \rfloor \\
&= f_n(x)
\end{align*}
- Suppose \(0 \leq t < \frac1n\), then note that \(\left \lfloor t + \frac{k}{n} \right \rfloor = 0\) for \(0 \leq k \leq n - 1\) and \(\lfloor n t \rfloor = 0\) since \(nt < 1\)
- Since \(f_n(x)\) is zero on \([0, \tfrac1n)\) and periodic with period \(\tfrac1n\) it must be constantly zero
- Claim: \(\left\lfloor \frac{x}{2} \right\rfloor + \left\lfloor \frac{x+1}{2} \right\rfloor = \lfloor x \rfloor\)
Proof: Suppose \(x = n + \epsilon\) where \(0 \leq \epsilon < 1\), ie \(n = \lfloor x \rfloor\), then consider two cases:
Case 1: \(n = 2k\)
\begin{align*}
\left\lfloor \frac{x}{2} \right\rfloor + \left\lfloor \frac{x+1}{2} \right\rfloor &= \left\lfloor \frac{n + \epsilon}{2} \right\rfloor + \left\lfloor \frac{n + \epsilon+1}{2} \right\rfloor \\
&= \left\lfloor \frac{2k + \epsilon}{2} \right\rfloor + \left\lfloor \frac{2k + \epsilon+1}{2} \right\rfloor \\
&= k + \left\lfloor \frac{\epsilon}{2} \right\rfloor + k + \left\lfloor \frac{\epsilon+1}{2} \right\rfloor \\
&= 2k \\
&= n
\end{align*}
Case 2: \(n = 2k + 1\)
\begin{align*}
\left\lfloor \frac{x}{2} \right\rfloor + \left\lfloor \frac{x+1}{2} \right\rfloor &= \left\lfloor \frac{n + \epsilon}{2} \right\rfloor + \left\lfloor \frac{n + \epsilon+1}{2} \right\rfloor \\
&= \left\lfloor \frac{2k +1+ \epsilon}{2} \right\rfloor + \left\lfloor \frac{2k +1+ \epsilon+1}{2} \right\rfloor \\
&= k + \left\lfloor \frac{\epsilon+1}{2} \right\rfloor + k +1+ \left\lfloor \frac{\epsilon}{2} \right\rfloor \\
&= 2k +1\\
&= n
\end{align*}
as required.
- Since \(\left \lfloor \frac{x+1}{2} \right \rfloor = \lfloor x \rfloor - \lfloor \frac{x}{2} \rfloor\) and in general, \(\left \lfloor \frac{x+2^k}{2^{k+1}} \right \rfloor = \lfloor \frac{x}{2^k} \rfloor - \lfloor \frac{x}{2^{k+1}} \rfloor\) and so in general:
\begin{align*}
\sum_{k=0}^\infty \left \lfloor \frac{x+2^k}{2^{k+1}} \right \rfloor &= \sum_{k=0}^\infty \left ( \left \lfloor \frac{x}{2^k} \right \rfloor -\left \lfloor \frac{x}{2^{k+1}} \right \rfloor \right) \\
&= \lfloor x \rfloor
\end{align*}
The sequence \(F_n\), for \(n = 0, 1, 2, \ldots\), is defined by \(F_0 = 0\), \(F_1 = 1\) and by \(F_{n+2} = F_{n+1} + F_n\) for \(n \geqslant 0\).
Prove by induction that, for all positive integers \(n\),
\[\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \mathbf{Q}^n,\]
where the matrix \(\mathbf{Q}\) is given by
\[\mathbf{Q} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}.\]
- By considering the matrix \(\mathbf{Q}^n\), show that \(F_{n+1}F_{n-1} - F_n^2 = (-1)^n\) for all positive integers \(n\).
- By considering the matrix \(\mathbf{Q}^{m+n}\), show that \(F_{m+n} = F_{m+1}F_n + F_m F_{n-1}\) for all positive integers \(m\) and \(n\).
- Show that \(\mathbf{Q}^2 = \mathbf{I} + \mathbf{Q}\).
In the following parts, you may use without proof the Binomial Theorem for matrices:
\[(\mathbf{I} + \mathbf{A})^n = \sum_{k=0}^{n} \binom{n}{k} \mathbf{A}^k.\]
- Show that, for all positive integers \(n\),
\[F_{2n} = \sum_{k=0}^{n} \binom{n}{k} F_k\,.\]
- Show that, for all positive integers \(n\),
\[F_{3n} = \sum_{k=0}^{n} \binom{n}{k} 2^k F_k\]
and also that
\[F_{3n} = \sum_{k=0}^{n} \binom{n}{k} F_{n+k}\,.\]
- Show that, for all positive integers \(n\),
\[\sum_{k=0}^{n} (-1)^{n+k} \binom{n}{k} F_{n+k} = 0\,.\]
Two sequences are defined by \(a_1 = 1\) and \(b_1 = 2\) and, for \(n \ge 1\),
\begin{equation*}
\begin{split}
a_{n+1} & = a_n+ 2b_n \,,
\\
b_{n+1} & = 2a_n + 5b_n \,.
\end{split}
\end{equation*}
Prove by induction that, for all \(n \ge 1\),
\[ a_n^2+2a_nb_n - b_n^2 = 1 \,. \tag{\(*\)}\]
- Let \(c_n = \dfrac{a_n}{b_n}\). Show that \(b_n \ge 2 \times 5^{n-1}\) and use \((*)\) to show that
\[ c_n \to \sqrt 2 -1 \text{ as } n\to\infty\,. \]
- Show also that \(c_n > \sqrt2 -1\) and hence that \(\dfrac2 {c_n+1} < \sqrt2 < c_n+1\).
Deduce that \(\dfrac{140}{99}< \sqrt{2} < \dfrac{99}{70 }\,\).
Show Solution
Claim \(a_n^2+2a_nb_n - b_n^2 = 1\) for all \(n \geq 1\)
Proof: (By induction)
Base case: (\(n = 1\)).
When \(n = 1\) we have \(a_1^2 + 2a_1 b_1-b_1^2 = 1^2+2\cdot1\cdot2-2^2 = 1\) as required.
(Inductive step). Now we assume our result is true for some \(n =k\), ie \(a_k^2+2a_kb_k - b_k^2 = 1\), now consider \(n = k+1\)
\begin{align*}
&& a_{k+1}^2+2a_{k+1}b_{k+1} - b_{k+1}^2 &= (a_k+2b_k)^2+2(a_k+2b_k)(2a_k+5b_k) - (2a_k+5b_k)^2 \\
&&&= a_k^2+4a_kb_k+4b_k^2 +4a_k^2+18a_kb_k+20b_k^2 - 4a_k^2-20a_kb_k-25b_k^2 \\
&&&= (1+4-4)a_k^2+(4+18-20)a_kb_k +(4+20-25)b_k^2 \\
&&&= a_k^2+2a_kb_k -b_k^2 = 1
\end{align*}
Therefore since our statement is true for \(n = 1\) and when it is true for \(n=k\) it is true for \(n=k+1\) by the POMI it is true for \(n \geq 1\)
- Notice that \(b_{n+1} \geq 5 b_n\) and therefore \(b_n \geq 5^{n-1} b_1 = 2\cdot 5^{n-1}\), so
\begin{align*}
&& 1 &= a_n^2+2a_nb_n - b_n^2\\
\Rightarrow && \frac1{b_n^2} &= c_n^2 + 2c_n - 1 \\
\to && 0 &= c_n^2 + 2c_n - 1 \quad \text{ as } n\to \infty \\
\end{align*}
This has roots \(c = -1 \pm \sqrt{2}\), and since \(c_n > 0\) it must tend to the positive value, ie \(c_n \to \sqrt{2}-1\)
- Notice that \(c_n^2 + 2c_n - 1 > 0\) so either \(c_n > \sqrt{2}-1\) or \(c_n < -1-\sqrt{2}\), but again, since \(c_n > 0\) we must have \(c_n > \sqrt{2}-1\).
Therefore \(\sqrt{2} < c_n + 1\) and \(1+c_n > \sqrt{2} \Rightarrow \frac{1}{1+c_n} < \frac{\sqrt{2}}2 \Rightarrow \frac{2}{1+c_n} < \sqrt{2}\)
\begin{array}{c|c|c}
n & a_n & b_n \\ \hline
1 & 1 & 2 \\
2 & 5 & 12 \\
3 & 29 & 70
\end{array}
Therefore \(c_3 = \frac{29}{70}\) and so
\(\frac{2}{1 + \frac{29}{70}} = \frac{140}{99} < \sqrt{2} < \frac{29}{70} + 1 = \frac{99}{70}\)
Let
\[
S_n = \sum_{r=1}^n \frac 1 {\sqrt r \ }
\,,
\]
where \(n\) is a positive integer.
- Prove by induction that
\[
S_n \le 2\sqrt n -1\,
.
\]
- Show that \((4k+1)\sqrt{k+1} > (4k+3)\sqrt k\,\) for \(k\ge0\,\).
Determine the smallest number \(C\) such that
\[
S_n \ge 2\sqrt n + \frac 1 {2\sqrt n} -C
\,.\]
Show Solution
- Claim: \(S_n \leq 2\sqrt{n} -1\).
Proof: (By induction)
(Base case: \(n = 1\)). \(\frac{1}{\sqrt{1}} \leq 1 = 2 \cdot \sqrt1 - 1\). Therefore the base case is true.
(Inductive step): Suppose our result is true for \(n = k\). Then consider \(n = k+1\).
\begin{align*}
&& \sum_{r=1}^{k+1} \frac{1}{\sqrt{r}} &=\sum_{r=1}^{k} \frac{1}{\sqrt{r}} + \frac{1}{\sqrt{k+1}} \\
&&&\leq 2\sqrt{k} - 1 + \frac{1}{\sqrt{k+1}} \\
&&&= \frac{2 \sqrt{k}\sqrt{k+1}+1}{\sqrt{k+1}} - 1 \\
&&&\underbrace{\leq}_{AM-GM} \frac{(k+k+1)+1}{\sqrt{k+1}} - 1 \\
&&&=\frac{2(k+1)}{\sqrt{k+1}} - 1 \\
&&&= 2\sqrt{k+1}-1
\end{align*}
Therefore, since if our statement is true for \(n = k\), it is also true for \(n = k+1\). By the principle of mathematical induction we can say that it is true for all \(n \geq 1, n \in \mathbb{Z}\)
- Claim: \((4k+1)\sqrt{k+1} > (4k+3)\sqrt k\,\) for \(k\ge0\,\)
Proof: \begin{align*}
&& (4k+1)\sqrt{k+1} &> (4k+3)\sqrt k \\
\Leftrightarrow && (4k+1)^2(k+1) &> (4k+3)^2k \\
\Leftrightarrow && (16k^2+8k+1)(k+1) &> (16k^2 + 24k+9)k \\
\Leftrightarrow && 16 k^3 + 24 k^2 + 9 k +1&> 16k^3 + 24k^2+9k
\end{align*}
But this last inequality is clearly true, hence our original inequality is true.
Suppose \(S_n \geq 2\sqrt{n} + \frac{1}{2 \sqrt{n}} - C\), then adding \(\frac{1}{\sqrt{n+1}}\) to both sides we have:
\begin{align*}
S_{n+1} &\geq 2\sqrt{n} + \frac{1}{2 \sqrt{n}} - C + \frac{1}{\sqrt{n+1}} \\
&= 2\sqrt{n+1} + \frac{1}{2\sqrt{n+1}} - C + \frac{1}{2\sqrt{n+1}} +\frac{1}{2 \sqrt{n}} +2(\sqrt{n} - \sqrt{n+1})\\
&= 2\sqrt{n+1} + \frac{1}{2\sqrt{n+1}} - C + \frac{1}{2\sqrt{n+1}} +\frac{1}{2 \sqrt{n}} -\frac{2}{\sqrt{n+1} + \sqrt{n}}\\
\end{align*}
Therefore as long as the inequality is satisfied for \(n=1\), ie \(1 \geq 2\sqrt{1} + \frac{1}{2 \sqrt{1}} - C = \frac52 - C \Rightarrow C \geq \frac32\)
Let
\[
T _n =
\left( \sqrt{a+1} + \sqrt a\right)^n\,,
\]
where \(n\) is a positive integer and \(a\) is any given positive integer.
- In the case when \(n\) is even, show
by induction that
\(T_n\) can be written in the form
\[
A_n +B_n \sqrt{a(a+1)}\,,
\]
where
\(A_n\) and \(B_n\) are integers (depending on \(a\) and \(n\))
and \(A_n^2 =a(a+1)B_n^2 +1\).
- In the case when \(n\) is odd, show by considering
\((\sqrt{a+1} +\sqrt a)T_m\) where \(m\) is even, or otherwise,
that \(T_n\)
can be written in the form
\[
C_n \sqrt {a+1} + D_n \sqrt a \,,
\]
where \(C_n\) and \(D_n\) are integers (depending on \(a\) and \(n\)) and
\( (a+1)C_n^2 = a D_n^2 +1\,\).
- Deduce that, for each \(n\), \(T_n\) can be written
as the sum of the square roots of two consecutive integers.
Show Solution
- Claim: For all \(n \geq 1\) \(T_{2n} = A_{2n} + B_{2n}\sqrt{a(a+1)}\) where \(A_{2n}, B_{2n}\) are integers and \(A_{2n}^2 = a(a+1)B_{2n}^2+1\)
Proof: (By induction)
Base case: \(n =1\).
\begin{align*}
&& T_2 &= (\sqrt{a+1}+\sqrt{a})^2 \\
&&&= a+1+2\sqrt{a(a+1)}+a \\
&&&=2a+1+2\sqrt{a(a+1)} \\
\Rightarrow && A_2 &= 2a+1 \\
&& B_2 &= 2 \\
&& A_2^2 &= 4a^2+4a+1 \\
&& a(a+1)B_1^2 + 1 &= 4a^2+4a+1
\end{align*}
Therefore our base case is true. Suppose it is true for some \(n = k\) then consider \(n = k+1\) we must have \(T_{2k} = A_{2k}+B_{2k}\sqrt{a(a+1)}\)
\begin{align*}
&& T_{2(k+1)} &= T_{2k} (\sqrt{a+1}+\sqrt{a})^2 \\
&&&= \left (A_{2k}+B_{2k}\sqrt{a(a+1)} \right)\left (2a+1+2\sqrt{a(a+1)} \right) \\
&&&= (2a+1)A_{2k}+2a(a+1)B_{2k} + (2A_{2k}+(2a+1)B_{2k})\sqrt{a(a+1)} \\
\Rightarrow && A_{2(k+1)} &= (2a+1)A_{2k}+2a(a+1)B_{2k} \in \mathbb{Z} \\
&& B_{2(k+1)} &= 2A_{2k}+(2a+1)B_{2k} \in \mathbb{Z} \\
&& A_{2(k+1)}^2 &= \left ( (2a+1)A_{2k}+2a(a+1)B_{2k} \right)^2 \\
&&&= (2a+1)^2A_{2k}^2+4a^2(a+1)^2B_{2k}^2+4a(a+1)(2a+1)A_{2k}B_{2k} \\
&&&= a^2(a+1)^2(2a+1)^2B_{2k}^2+(2a+1)^2\\
&&&\quad\quad+4a^2(a+1)^2B_{2k}^2+4a(a+1)(2a+1)A_{2k}B_{2k}\\
&& a(a+1)B_{2(k+1)}^2 + 1 &= a(a+1)\left ( 2A_{2k}+(2a+1)B_{2k} \right)^2 \\
&&&= 4a(a+1)A_{2k}^2 + 4a(a+1)(2a+1)A_{2k}B_{2k} + a(a+1)(2a+1)^2B_{2k}^2 + 1\\
&&&= 4a^2(a+1)^2B_{2k}^2+4a(a+1) + \\
&&&\quad\quad+ 4a(a+1)(2a+1)A_{2k}B_{2k} + a(a+1)(2a+1)^2B_{2k}^2 + 1
\end{align*}
So our relation holds ad therefore by induction we're done.
- When \(n\) is odd, notice that
\begin{align*}
&& T_n &= (\sqrt{a+1}+\sqrt{a})(A_m+B_m\sqrt{a(a+1)})\\
&&&= \sqrt{a+1}(\underbrace{A_m+aB_m}_{C_n})+\sqrt{a}(\underbrace{(a+1)B_m+A_m}_{D_n}) \\
\\
&& (a+1)C_n^2 &= (a+1)(A_m+aB_m)^2 \\
&&&= (a+1)(A_m^2+2aA_mB_m+B_m^2) \\
&&&= (a+1)(a(a+1)B_m^2+1+2aA_mB_m+B_m^2) \\
&&&= a(a+1)^2B_m^2 + 2a(a+1)A_mB_m+(a+1)B_m^2+a+1 \\
&& aD_n^2+1 &= a((a+1)^2B_m + 2(a+1)A_mB_m + A_m^2)+1 \\
&&&= a(a+1)^2B_m + 2a(a+1)A_mB_m + aB_{m}^2+a+1
\end{align*}
- For even \(n\) \(T_n = \sqrt{a(a+1)B_{2n}^2+1} + \sqrt{a(a+1)B_{2n}^2}\)
For odd \(n\), \(T_n = \sqrt{aD_n^2+1}+ \sqrt{aD_n^2}\) therefore it is always the sum of the square root of two consecutive integers.
The functions \({\rm T}_n(x)\), for \(n=0\), 1, 2, \(\ldots\,\), satisfy
the recurrence relation
\[
{\rm T}_{n+1}(x) -2x {\rm T}_n(x) + {\rm T}_{n-1}(x) =0\,
\ \ \ \ \ \ \ (n\ge1).
\tag{\(*\)}
\]
Show by induction that
\[
\left({\rm T}_n(x)\right)^2 - {\rm T}_{n-1}(x) {\rm T}_{n+1}(x) = \f(x)\,,
\]
where \(\f(x) = \left({\rm T}_1(x)\right)^2 - {\rm T}_0(x){\rm T}_2(x)\,\).
In the case \(\f(x)\equiv 0\), determine (with proof) an expression
for \({\rm T}_n(x)\) in terms of \({\rm T}_0(x)\) (assumed to be non-zero)
and \({\rm r}(x)\), where
\({\rm r}(x) = {\rm T}_1(x)/ {\rm T}_0(x)\).
Find the two possible expressions for \({\rm r}(x)\)
in terms of \(x\).
%Conjecture (without proof) the general form of the solution of \((*)\).
A sequence of numbers, \(F_1, F_2, \ldots\), is defined by
\(F_1=1, F_2=1\), and
\[
F_n=F_{n-1}+F_{n-2}\, \quad \text{for \(n\ge 3\)}.
\]
- Write down the values of \(F_3, F_4, \ldots , F_8\).
- Prove that \(F^{\vphantom{2}}_{2k+3}F^{\vphantom{2}}_{2k+1} -F_{2k+2}^2 = -F^{\vphantom{2}}_{2k+2}F^{\vphantom{2}}_{2k}+F_{2k+1}^2\,\).
- Prove by induction or otherwise that
\(F^{\vphantom{2}}_{2n+1}F^{\vphantom{2}}_{2n-1}-F^2_{2n}=1\,\) and deduce that \(F^2_{2n}+1\,\) is divisible by \(F^{\vphantom{2}}_{2n+1}\,.\)
- Prove that \(F^2_{2n-1}+1\,\) is divisible by \(F^{\vphantom{2}}_{2n+1}\,.\)
It is given that \(\sum\limits_{r=-1}^ {n} r^2\) can be written in the form \(pn^3 +qn^2+rn+s\,\), where \(p\,\), \(q\,\), \(r\,\) and \(s\) are numbers. By setting \(n=-1\), \(0\), \(1\) and \(2\), obtain four equations that must be satisfied by \(p\,\), \(q\,\), \(r\,\) and \(s\)
and hence show that
\[
{ \sum\limits_{r=0} ^n} r^2= {\textstyle \frac16} n(n+1)(2n+1)\;.
\]
Given that \(\sum\limits_{r=-2}^ nr^3\) can be written in the form \(an^4 +bn^3+cn^2+dn +e\,\), show similarly that
\[
{ \sum\limits_{r=0} ^n} r^3= {\textstyle \frac14} n^2(n+1)^2\;.
\]
Show Solution
\begin{align*}
n = -1: && (-1)^2 &= s - r+q -p \\
n = 0: && 1 + 0 &= s \\
n = 1: && 1 + 1 &= s + r + q + p \\
n = 2: && 2 + 2^2 &= s + 2r + 4q + 8p \\
\Rightarrow &&& \begin{cases}
1 &= s \\
1 &= s - r + q - p \\
2 &= s + r + q + p \\
6 &= s + 2r + 4q + 8p
\end{cases} \\
\Rightarrow && s &= 1 \\
&& q &= \frac12 \\
&&& \begin{cases} \frac12 &= r + p \\
3 &= 2r + 8p \end{cases} \\
\Rightarrow && r &= \frac16 \\
&& p &= \frac13 \\
\Rightarrow && \sum_{r=0}^n r^2 &= 1 + \frac16 n + \frac12 n^2 + \frac13 n^3 - (-1)^2 \\
&&&= \frac{n}{6} \l 1 + 3n + 2n^2 \r \\
&&&= \frac{n(n+1)(2n+1)}{6}
\end{align*}
Similarly,
\begin{align*}
n = -2: && (-2)^3 &= e - 2d + 4c - 8b + 16a \\
n = -1: && -8 + (-1)^3 &= e -d+c-b+a \\
n = 0: && -9 + 0^3 &= e \\
n = 1: && -9 + 1^3 &= e+d+c+b+a \\
n = 2: && -8 + 2^3 &= e+2d+4c+8b+16a \\
\Rightarrow &&& \begin{cases}
-9 &= e \\
-9 &= e - d+c -b + a \\
-8 &= e +d+c+b+a \\
-8 &= e-2d+4c-8b+16a \\
0 &= e+2d+4c+8b+16a \\
\end{cases} \\
\Rightarrow && e &= -9 \\
\Rightarrow &&& \begin{cases}
1 &= 2c+2a \\
10 &= 8c+32a \\
1 &= 2d+2b \\
8 &= 4d+16b \\
\end{cases} \\
\Rightarrow && a &= \frac14 \\
&& c &= \frac14 \\
&& b &= \frac12 \\
&& d &= 0 \\
\\
\Rightarrow && \sum_{r=0}^n r^3 &= -9 + \frac14n^2 + \frac12 n^3+\frac14 n^4 -((-1)^3+(-2)^3) \\
&&&= \frac14n^2 \l1 + 2n+n^2\r \\
&&&= \frac{n^2(n+1)^2}{4}
\end{align*}
as required
The \(n\)th Fermat number, \(F_n\), is defined by
\[
F_n = 2^{2^n} +1\, ,
\ \ \ \ \ \ \ n=0, \ 1, \ 2, \ \ldots \ ,
\]
where \(\ds 2^{2^n}\) means \(2\) raised to the power \(2^n\,\).
Calculate \(F_0\), \(F_1\), \(F_2\) and \(F_3\,\). Show that,
for \(k=1\), \(k=2\) and \(k=3\,\),
$$
F_0F_1 \ldots F_{k-1} = F_k-2 \;. \tag{*}
$$
Prove, by induction, or otherwise, that
\((*)\) holds for all \(k\ge1\). Deduce that no two Fermat numbers
have a common factor greater than \(1\).
Hence
show that there are infinitely many prime numbers.
Show Solution
\begin{align*}
&& F_0 &= 2^{2^0}+1 \\
&&&= 2^1+1 = 3\\
&& F_1 &= 2^{2^1}+1 \\
&&&= 2^2+1 = 5 \\
&& F_2 &= 2^{2^2}+1 \\
&&&= 2^4+1 \\
&&&= 17 \\
&&F_3 &= 2^{2^3}+1 \\
&&&= 2^8+1 \\
&&&= 257 \\
\\
&& \text{empty product} &= 1\\
&& F_1 - 2 &= 3-2 = 1\\
\Rightarrow&& 1 &= F_1-2\\
&& F_0 &=3 \\
&& F_2-2 &= 3 \\
\Rightarrow && F_0 &= F_2 - 2\\
&& F_0F_1 &= 3 \cdot 5 = 15 \\
&& F_3-2 &= 17-2 = 15 \\
\Rightarrow && F_0F_1 &= F_3-2
\end{align*}
\begin{align*}
&& F_0 F_1 \cdots F_{k-1} &= \prod_{i=0}^{k-1} \left ( 2^{2^{i}}+1\right) \\
&&&= \sum_{l = \text{sum of }2^i} 2^l \\
&&&= \sum_{l=0}^{2^{k}-1}2^l \\
&&&= 2^{2^k}-1 \\
&&&= F_k-2
\end{align*}
Suppose \(p \mid F_a, F_b\) with \(b > a\), then \(p \mid 2=F_b - F_0\cdots F_a \cdots F_{b-1}\) therefore \(p = 1, 2\), but \(2 \nmid F_a\) for any \(a\). Therefore any number dividing two Fermat numbers is \(1\), ie they are all coprime.
Consider the smallest prime dividing \(F_n\) for each \(n\). Clearly these are all different since each \(F_n\) is coprime from all the others. Clearly there are infinitely many of time (since there are infinitely many \(F_n\)). Therefore there are infinitely many primes.
Let $$ {\rm S}_n(x)=\mathrm{e}^{x^3}{{\d^n}\over{\d x^n}}{(\mathrm{e}^{-x^3})}.$$
Show that \({\rm S}_2(x)=9x^4-6x\) and find \({\rm S}_3(x)\). Prove by induction on \(n\) that \({\rm S}_n(x)\) is a polynomial. By means of your induction argument, determine the order of this polynomial and the coefficient of the highest power of \(x\).
Show also that if \(\displaystyle \frac{\d S_n}{\d x}=0\) for some value \(a\) of \(x\), then \(S_n(a)S_{n+1}(a)\le0\).
Show Solution
\begin{align*}
&& S_2(x) &= e^{x^3} \frac{d^2}{\d x^2} \left [e^{-x^3} \right] \\
&&&= e^{x^3} \frac{d}{\d x} \left [e^{-x^3}(-3x^2) \right] \\
&&&= e^{x^3} \left [e^{-x^3}(9x^4-6x) \right] \\
&&&=9x^4-6x \\
\\
&& S_3(x) &= e^{x^3} \frac{\d^3}{\d x^3} \left [ e^{-x^3} \right]\\
&&&= e^{x^3} \frac{\d}{\d x} \left [ e^{-x^3}(9x^4-6x) \right ] \\
&&&= e^{x^3} e^{-x^3}\left [ (-3x^2)(9x^4-6x)+(36x^3-6) \right ] \\
&&&= -27x^6 +54x^3-6
\end{align*}
Claim: \(S_n\) is a polynomial of degree \(2n\) with leading coefficient \((-3)^n\).
Proof: Clearly this is true for \(n = 1, 2, 3\) by demonstration. Suppose it is true for some \(n = k\), then
\begin{align*}
&& S_k(x) &= e^{x^2} \frac{\d^k}{\d x^k} \left [ e^{x^3}\right] \\
&& (-3)^kx^{2k} +\cdots &= e^{x^3} \frac{\d^k}{\d x^k} \left [ e^{x^3}\right] \\
\Rightarrow && \frac{\d^k}{\d x^k} \left [ e^{x^3}\right] &= e^{-x^3} \left ( (-3)^kx^{2k} +\cdots\right) \\
\Rightarrow && \frac{\d^k}{\d x^k}\left [ e^{x^3}\right] &= e^{-x^3} (-3x^2)\left ( (-3)^kx^{2k} +\cdots\right) + e^{-x^3} S_k'(x) \\
&&&= e^{-x^3} \left (\underbrace{ (-3)^{k+1}x^{2k+2} + \cdots + S_k'(x)}_{\deg =2k+2}\right) \\
\Rightarrow && S_{k+1}(x) &= (-3)^{k+1}x^{2k+2} + \cdots + S_k'(x)
\end{align*}
And therefore \(S_{k+1}\) is a polynomial degree \(2(k+1)\) with leading coefficient \((-3)^{k+1}\) so by induction it's true for all \(n\).
If \(S'_n(a) = 0\) then \(S_{n+1}(a) = (-3a^2)S_n(a) + S_n'(a) \Rightarrow S_{n+1}(a)S_n(a) = -3 (aS_n(a))^2 \leq 0\)
Suppose that
$$3=\frac{2}{ x_1}=x_1+\frac{2}{ x_2}
=x_2+\frac{2}{ x_3}=x_3+\frac{2}{ x_4}=\cdots.$$
Guess an expression, in terms of \(n\), for \(x_n\).
Then, by induction or otherwise,
prove the correctness of your guess.
Show Solution
\begin{align*}
x_1 &= \frac{2}{3} \\
x_n &= \frac{2}{3-x_{n-1}} \\
x_2 &= \frac{2}{3 - \frac23} \\
&= \frac{6}7 \\
x_3 &= \frac{2}{3-\frac67} \\
&= \frac{14}{15} \\
x_4 &= \frac{2}{3 - \frac{14}{15}} \\
&= \frac{30}{31}
\end{align*}
Guess: \(x_n = \frac{2^{n+1}-2}{2^{n+1}-1}\).
Proof: (By induction)
(Base case): We have checked several initial cases.
(Inductive step): Suppose our formula is true for \(n = k\), then consider:
\begin{align*}
x_{k+1} &= \frac{2}{3 - x_{k}} \\
&= \frac{2}{3 - \frac{2^{k+1}-2}{2^{k+1}-1}}\tag{assumption} \\
&= \frac{2\cdot(2^{k+1}-1)}{3 \cdot(2^{k+1}-1) - (2^{k+1}-2) } \\
&= \frac{2^{k+2}-2}{2\cdot 2^{k+1} - 3 + 2 } \\
&= \frac{2^{k+2}-2}{ 2^{k+2} - 1 } \\
\end{align*}
Therefore, if our formula is true for \(n = k\) it is true for \(n = k+1\). Therefore by the principle of mathematical induction it is true for \(n \geq 1, n \in \mathbb{Z}\)
The Fibonacci numbers \(F_{n}\) are defined by the conditions
\(F_{0}=0\), \(F_{1}=1\) and
\[F_{n+1}=F_{n}+F_{n-1}\]
for all \(n\geqslant 1\). Show that \(F_{2}=1\),
\(F_{3}=2\), \(F_{4}=3\) and compute
\(F_{5}\), \(F_{6}\) and~\(F_{7}\).
Compute \(F_{n+1}F_{n-1}-F_{n}^{2}\) for a few values of \(n\); guess
a general formula and prove it by induction, or otherwise.
By induction on \(k\), or otherwise, show that
\[F_{n+k}=F_{k}F_{n+1}+F_{k-1}F_{n}\]
for all positive integers \(n\) and \(k\).
I have \(n\) fence posts placed in a line and, as part of my spouse's
birthday celebrations, I wish to paint them using three different
colours red, white and blue in such a way that no adjacent fence posts
have the same colours. (This allows the possibility of using fewer
than three colours as well as exactly three.) Let \(r_{n}\) be the
number of ways (possibly zero) that I can paint them if I paint the
first and the last post red and let \(s_{n}\) be the number of ways
that I can paint them if I paint the first post red but the last post
either of the other two colours. Explain why \(r_{n+1}=s_{n}\) and
find \(r_{n}+s_{n}.\) Hence find the value of \(r_{n+1}+r_{n}\) for
all \(n\geqslant1.\)
Prove, by induction, that
\[
r_{n}=\frac{2^{n-1}+2(-1)^{n-1}}{3}.
\]
Find the number of ways of painting \(n\) fence posts (where \(n\geqslant3\))
placed in a circle using three different colours in such a way that
no adjacent fence posts have the same colours.
Suppose that \(a_{i}>0\) for all \(i>0\). Show that
\[
a_{1}a_{2}\leqslant\left(\frac{a_{1}+a_{2}}{2}\right)^{2}.
\]
Prove by induction that for all positive integers \(m\)
\[
a_{1}\cdots a_{2^{m}}\leqslant\left(\frac{a_{1}+\cdots+a_{2^{m}}}{2^{m}}\right)^{2^{m}}.\tag{*}
\]
If \(n<2^{m}\), put \(b_{1}=a_{2},\) \(b_{2}=a_{2},\cdots,b_{n}=a_{n}\)
and \(b_{n+1}=\cdots=b_{2^{m}}=A\), where
\[
A=\frac{a_{1}+\cdots+a_{n}}{n}.
\]
By applying \((*)\) to the \(b_{i},\) show that
\[
a_{1}\cdots a_{n}A^{(2^{m}-n)}\leqslant A^{2^{m}}
\]
(notice that \(b_{1}+\cdots+b_{n}=nA).\) Deduce the (arithmetic mean)/(geometric
mean) inequality
\[
\left(a_{1}\cdots a_{n}\right)^{1/n}\leqslant\frac{a_{1}+\cdots+a_{n}}{n}.
\]
Show Solution
\begin{align*}
&& 0 &\leqslant (a_1 - a_2)^2 \\
&&&= a_1^2 -2a_1a_2 + a_2^2 \\
&&&= (a_1+a_2)^2 -4a_1a_2 \\
\Leftrightarrow && a_1a_2 &\leqslant \left ( \frac{a_1+a_2}2 \right)^2
\end{align*}
Claim: \((*)\) is true
Proof: (By induction)
We have already proven the base case.
Suppose it is true for some \(m\), then consider \(m+1\)
\begin{align*}
&& a_1 \cdots a_{2^m} &\leqslant \left ( \frac{a_1 + \cdots + a_{2^m}}{2^m} \right)^{2^m} \tag{by (*)} \\
&& a_{2^m+1} \cdots a_{2^{m+1}} &\leqslant \left ( \frac{a_{2^m+1} + \cdots + a_{2^{m+1}}}{2^m} \right)^{2^m} \tag{by (*)} \\
\Rightarrow && (a_1 \cdots a_{2^m})^{1/2^m} &\leqslant \left ( \frac{a_1 + \cdots + a_{2^m}}{2^m} \right) \\
&& (a_{2^m+1} \cdots a_{2^{m+1}})^{1/2^m} &\leqslant \left ( \frac{a_{2^m+1} + \cdots + a_{2^{m+1}}}{2^m} \right) \\
\Rightarrow && (a_1 \cdots a_{2^m})^{1/2^m} \cdot (a_{2^m+1} \cdots a_{2^{m+1}})^{1/2^m} &\leqslant \left ( \frac{ (a_1 \cdots a_{2^m})^{1/2^m} +(a_{2^m+1} \cdots a_{2^{m+1}})^{1/2^m} }{2} \right )^2 \\
&&&\leqslant \left ( \frac{ \frac{a_1 + \cdots + a_{2^m}}{2^m}+\frac{a_{2^m+1} + \cdots + a_{2^{m+1}}}{2^m} }{2} \right )^2 \\
&&&\leqslant \left ( \frac{ a_1 + \cdots + a_{2^m}+a_{2^m+1} + \cdots + a_{2^{m+1}} }{2^{m+1}} \right )^2 \\
\Rightarrow && a_1 \cdots a_{2^{m+1}} &\leqslant \left ( \frac{a_1 + \cdots + a_{2^{m+1}}}{2^{m+1}} \right)^{2^{m+1}}
\end{align*}
Which is precisely \((*)\) for \(m+1\). Therefore our statement is true by induction.
Suppose \(n < 2^m\) and \(b_1 = a_1, b_2 = a_2, \cdots b_n = a_n\) and \(b_{n+1} = \cdots = b_{2^m} = A\) where \(A = \frac{a_1 + \cdots + a_n}{n}\) then
\begin{align*}
&& b_1 \cdots b_n \cdot b_{n+1} \cdots b_{2^m} &\leq \left ( \frac{b_1 + \cdots + b_n + b_{n+1} + \cdots + b_{2^m}}{2^{m}} \right)^{2^m} \\
\Leftrightarrow && a_1 \cdots a_n \cdot A^{2^m-n} &\leq \left ( \frac{a_1 + \cdots + a_n + (2^m-n)A}{2^m} \right)^{2^m} \\
&&&= \left ( \frac{nA + (2^m - n)A}{2^m} \right)^{2^m} \\
&&&= A^{2^m} \\
\Rightarrow && a_1 \cdots a_n &\leq A^n \\
\Rightarrow && (a_1 \cdots a_n)^{1/n} &\leq A = \frac{a_1 + \cdots + a_n}{n}
\end{align*}
Let \(\mathrm{g}(x)=ax+b.\) Show that, if \(\mathrm{g}(0)\) and \(\mathrm{g}(1)\) are integers, then \(\mathrm{g}(n)\) is an integer for all integers \(n\).
Let \(\mathrm{f}(x)=Ax^{2}+Bx+C.\) Show that, if \(\mathrm{f}(-1),\mathrm{f}(0)\) and \(\mathrm{f}(1)\) are integers, then \(\mathrm{f}(n)\) is an integer for all integers \(n\).
Show also that, if \(\alpha\) is any real number and \(\mathrm{f}(\alpha-1),\) \(\mathrm{f}(\alpha)\) and \(\mathrm{f}(\alpha+1)\) are integers, then \(\mathrm{f}(\alpha+n)\) is an integer for all integers \(n\).
Show Solution
If \(g(0) \in \mathbb{Z} \Rightarrow b \in \mathbb{Z}\). If \(g(1) \in \mathbb{Z} \Rightarrow a+b \in \mathbb{Z} \Rightarrow a \in \mathbb{Z}\), therefore \(a \cdot n + b \in \mathbb{Z}\), in particular \(g(n) \in \mathbb{Z}\) for all integers \(n\).
\(f(0) \in \mathbb{Z} \Rightarrow C \in \mathbb{Z}\), \(f(1) \in \mathbb{Z} = A+ B + C \in \mathbb{Z} \Rightarrow A+ B \in \mathbb{Z}\)
\(f(-1) \in \mathbb{Z} = A- B + C \in \mathbb{Z} \Rightarrow A- B \in \mathbb{Z}\)
\(\Rightarrow 2A, 2B \in \mathbb{Z}\)
\begin{align*}
f(n) &= An^2 + Bn + C \\
&= An^2-An + An+Bn + C \\
&= 2A \frac{n(n-1)}2 + (A+B)n + C \\
&\in \mathbb{Z}
\end{align*}
Consider \(g(x) = f(x + \alpha)\), therefore \(g(0), g(1), g(-1) \in \mathbb{Z} \Rightarrow g(n) \in \mathbb{Z} \Rightarrow f(n+\alpha) \in \mathbb{Z}\)
A plane contains \(n\) distinct given lines, no two of which are parallel, and no three of which intersect at a point. By first considering the cases \(n=1,2,3\) and \(4\), provide and justify, by induction or otherwise, a formula for the number of line segments (including the infinite segments).
Prove also that the plane is divided into \(\frac{1}{2}(n^{2}+n+2)\) regions (including those extending to infinity).
Show Solution
With \(n=1\) line, the plane is divided in half.
With \(n=2\) lines the plane is divided into four pieces. (Each of the previous pieces are split in half)
With \(n=3\) lines the plane is divided into up to \(7\) pieces. (The new line crosses two lines in two places dividing \(3\) regions into \(2\), thus increasing the number of regions by \(3\)).
With \(n=4\) lines the plane is divided into \(11\) pieces. (The new line crosses three lines in three places doubling the number of regions of \(4\) places).
Claim: With \(n\) lines the plane is divided into \(\frac12(n^2+n+2)\) regions.
Proof: (By induction)
(Base case) When \(n=1\) clearly the line is divided into \(2\) regions, and \(\frac12 (1^2 + 1^2 + 2) = 2\) so the base case is true.
(Inductive step) Suppose our formula is true for \(n=k\), so we have placed \(k\) lines in general position and divided the plane into \(\frac12(k^2+k+2)\) regions. When we place a new line it will meet those \(k\) lines in \(k\) places (since no lines are parallel) and there will be k+1 regions the line will run through (since no three lines meet at a point). Each of those \(k+1\) regios is now split in half, so there are \(k+1\) "new regions".
Therefore there are now \(\frac12(k^2+k+2)+(k+1) = \frac12(k^2+k+1+2k+2) = \frac12 ((k+1)^2+(k+1)+1)\) regions, ie our hypothesis is true for \(n=k+1\).
(Conclusion) Therefore since our statement is true for \(n=1\) and since if it is true for some \(n=k\) it is true for \(n=k+1\) by the principle of mathematical induction it is true for all \(n \geq 1\)
Proof: (Alternative).
There are \(\binom{n}{2}\) places where the lines meet. Each intersection is the most extreme point (say lowest) for one region (if two are tied, rotate by a very small amount) so this is a unique mapping. There will be \(n+1\) regions which are infinite and don't have a most extreme point, hence \(\binom{n}{2} + n+1 = \frac12(n^2-n)+n+1 = \frac12(n^2+n+2)\)
The Bernoulli polynomials \(P_{n}(x)\), where \(n\) is a non-negative integer, are defined by \(P_{0}(x)=1\) and, for \(n\geqslant1\),
\[
\frac{\mathrm{d}P_{n}}{\mathrm{d}x}=nP_{n-1}(x),\qquad\int_{0}^{1}P_{n}(x)\,\mathrm{d}x=0
\]
Show by induction or otherwise, that
\[
P_{n}(x+1)-P_{n}(x)=nx^{n-1},\quad\mbox{ for }n\geqslant1.
\]
Deduce that
\[
n\sum_{m=0}^{k}m^{n-1}=P_{n}(k+1)-P_{n}(0)
\]
Hence show that \({\displaystyle \sum_{m=0}^{1000}m^{3}=(500500)^{2}}\)
Show Solution
\(\displaystyle \int_x^{x+1} nP_{n-1}(x) \, dx = P_n(x+1) - P_n(x)\)
Claim: \(P_{n}(x+1)-P_{n}(x)=nx^{n-1},\) for \(n \geq 1\)
Proof: (By induction). (Base case, \(n=1\)).
\(P_1(x) = x - \frac12\), \(P_1(x+1) - P_1(x) = 1 x^{0}\) as required.
Assume the equation is true for \(n = k\). So \(P_k(x+1) - P_k(x) = kx^{k-1}\) now consider
\begin{align*}
P_{k+1}(x+1) - P_{k+1}(x) &= \int_0^{x+1} (k+1) P_k(t) \d t + P_{k+1}(0)- \int_0^{x} (k+1) P_k(t) \d t - P_{k+1}(0) \\
&= \int_0^x (k+1)(P_k(t+1)-P_k(t)) \d t + \int_0^1 (k+1)P_k(t) \d t \\
&= (k+1)x^{k} + 0
\end{align*}
So by induction we are done.
\begin{align*}
n\sum_{m=0}^{k}m^{n-1} &= \sum_{m=0}^{k}n \cdot m^{n-1} \\
&= \sum_{m=0}^{k}\l P_n(m+1)-P_n(m) \r \\
&= P_n(k+1) - P_n(0)
\end{align*}
We need to find \(P_4\)
\begin{align*}
P_0(x) &= 1 \\
P_1(x) &= x - \frac12 \\
P_2(x) &= x^2 -x - \int_0^1 \l x^2 - x \r \d x \\
&= x^2 - x + \frac16 \\
P_3(x) &= x^3 -\frac{3}{2}x^2 + \frac12x - \int_0^1 \l x^3 -\frac{3}{2}x^2 + \frac12x \r \d x \\
&= x^3 -\frac{3}{2}x^2 + \frac12x \\
P_4(x) &= x^4 - 2x^3 + x^2 + c
\end{align*}
Therefore the sum we are interested in is \(\frac14 \l P_4(1001) - P_4(0) \r = \frac14 (1001)^2 (1001-1)^2 = (1001 \cdot 500)^2 = (500500)^2\)