12 exam-style questions covering sums, divisibility, inequalities and matrix powers. Tap Show answer for full working.
Prove by induction that \( \displaystyle\sum_{r=1}^{n} r = \dfrac{n(n+1)}{2} \) for all positive integers \( n \).
Base: \( n=1 \): LHS \(=1\), RHS \(=1\cdot2/2=1\). True.
Assume true for \( n=k \): \( \sum_{r=1}^k r = k(k+1)/2 \).
Step: \( \sum_{r=1}^{k+1} r = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2 \).
Hence true for all positive integers \( n \) by induction.
Prove by induction that \( 3^n - 1 \) is divisible by 2 for all positive integers \( n \).
Base: \( n=1 \): \( 3-1=2 \), divisible by 2.
Assume \( 3^k - 1 = 2m \) for some integer \( m \).
Step: \( 3^{k+1} - 1 = 3\cdot 3^k - 1 = 3(2m+1) - 1 = 6m + 3 - 1 = 6m + 2 = 2(3m+1) \), divisible by 2.
Hence true for all positive integers \( n \).
Prove by induction that \( \displaystyle\sum_{r=1}^{n} r^2 = \dfrac{n(n+1)(2n+1)}{6} \) for all positive integers \( n \).
Base: \( n=1 \): LHS \(=1\), RHS \(=1\cdot2\cdot3/6=1\). True.
Assume true for \( n=k \).
Step: \( \sum_1^{k+1} r^2 = \dfrac{k(k+1)(2k+1)}{6} + (k+1)^2 = (k+1)\Big[ \dfrac{k(2k+1)}{6} + (k+1) \Big] = (k+1)\dfrac{2k^2 + k + 6k + 6}{6} = (k+1)\dfrac{2k^2 + 7k + 6}{6} = (k+1)\dfrac{(2k+3)(k+2)}{6} = \dfrac{(k+1)(k+2)(2k+3)}{6} \).
True for all \( n \).
Prove by induction that \( n^3 + 2n \) is divisible by 3 for all positive integers \( n \).
Base: \( n=1 \): \( 1+2=3 \), divisible by 3.
Assume \( k^3 + 2k = 3m \).
Step: \( (k+1)^3 + 2(k+1) = k^3 + 3k^2 + 3k + 1 + 2k + 2 = (k^3 + 2k) + 3k^2 + 3k + 3 = 3m + 3(k^2 + k + 1) \), divisible by 3.
Prove by induction that \( 5^{2n} - 1 \) is divisible by 24 for all positive integers \( n \).
Base: \( n=1 \): \( 25-1=24 \), yes.
Assume \( 5^{2k}-1 = 24m \).
Step: \( 5^{2(k+1)} - 1 = 5^{2k+2} - 1 = 25\cdot 5^{2k} - 1 = 25(24m + 1) - 1 = 600m + 25 - 1 = 600m + 24 = 24(25m + 1) \).
Prove by induction that \( \displaystyle\sum_{r=1}^{n} r\cdot r! = (n+1)! - 1 \) for all positive integers \( n \).
Base: \( n=1 \): \( 1\cdot1! = 1 \), \( 2! - 1 = 1 \). True.
Assume true for \( n=k \).
Step: \( \sum_1^{k+1} r\cdot r! = (k+1)! - 1 + (k+1)\cdot(k+1)! = (k+1)! - 1 + (k+1)! = (k+2)(k+1)! - 1 = (k+2)! - 1 \).
Prove by induction that \( 2^n > n^2 \) for all integers \( n \geq 5 \).
Base: \( n=5 \): \( 32 > 25 \). True.
Assume \( 2^k > k^2 \) for some \( k \geq 5 \).
Step: \( 2^{k+1} = 2\cdot 2^k > 2k^2 \). Need \( 2k^2 \geq (k+1)^2 = k^2 + 2k + 1 \), i.e. \( k^2 - 2k - 1 \geq 0 \), true for \( k \geq 5 \) (since roots of \( k^2-2k-1=0 \) are \( 1\pm\sqrt{2} \), positive root \( \approx 2.41 \)).
Thus \( 2^{k+1} > (k+1)^2 \). True for all \( n \geq 5 \).
Let \( \mathbf{A} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \). Prove by induction that \( \mathbf{A}^n = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix} \) for all positive integers \( n \).
Base: \( n=1 \): true.
Assume \( \mathbf{A}^k = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix} \).
Step: \( \mathbf{A}^{k+1} = \mathbf{A}^k \mathbf{A} = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 1+k \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & k+1 \\ 0 & 1 \end{pmatrix} \).
Prove by induction that \( \displaystyle\sum_{r=1}^{n} \dfrac{1}{r(r+1)} = 1 - \dfrac{1}{n+1} \) for all positive integers \( n \).
Base: \( n=1 \): \( 1/(1\cdot2)=1/2 \), \( 1-1/2=1/2 \). True.
Assume true for \( n=k \).
Step: \( \sum_1^{k+1} = 1 - 1/(k+1) + 1/((k+1)(k+2)) = 1 - \dfrac{k+2-1}{(k+1)(k+2)} = 1 - \dfrac{k+1}{(k+1)(k+2)} = 1 - 1/(k+2) \).
Prove by induction that \( 7^n - 2^n \) is divisible by 5 for all positive integers \( n \).
Base: \( n=1 \): \( 7-2=5 \). True.
Assume \( 7^k - 2^k = 5m \).
Step: \( 7^{k+1} - 2^{k+1} = 7\cdot 7^k - 2\cdot 2^k = 7(5m + 2^k) - 2\cdot 2^k = 35m + 7\cdot 2^k - 2\cdot 2^k = 35m + 5\cdot 2^k = 5(7m + 2^k) \).
Prove by induction that \( (1+x)^n \geq 1 + nx \) for all integers \( n \geq 1 \) and all real \( x \geq -1 \).
Base: \( n=1 \): \( 1+x \geq 1+x \). Equality holds.
Assume \( (1+x)^k \geq 1 + kx \) for \( k \geq 1 \), \( x \geq -1 \).
Step: \( (1+x)^{k+1} = (1+x)(1+x)^k \geq (1+x)(1+kx) = 1 + kx + x + kx^2 = 1 + (k+1)x + kx^2 \).
Since \( x \geq -1 \) and \( k \geq 1 \), \( kx^2 \geq 0 \) when \( x \geq 0 \); when \( -1 \leq x < 0 \), \( kx^2 \geq 0 \) still. Thus \( \geq 1 + (k+1)x \).
(Strict care at \( x=-1 \): both sides zero or check separately; holds.)
Let \( \mathbf{M} = \begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix} \). Prove by induction that \( \mathbf{M}^n = \begin{pmatrix} 2^n & n\cdot 2^{n-1} \\ 0 & 2^n \end{pmatrix} \) for all positive integers \( n \).
Base: \( n=1 \): \( \begin{pmatrix}2&1\\0&2\end{pmatrix} = \begin{pmatrix}2&1\cdot 2^0\\0&2\end{pmatrix} \). True.
Assume true for \( n=k \).
Step: \( \mathbf{M}^{k+1} = \mathbf{M}^k \mathbf{M} = \begin{pmatrix} 2^k & k 2^{k-1} \\ 0 & 2^k \end{pmatrix}\begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix} = \begin{pmatrix} 2^{k+1} & 2^k + 2k\cdot 2^{k-1} \\ 0 & 2^{k+1} \end{pmatrix} = \begin{pmatrix} 2^{k+1} & 2^k + k 2^k \\ 0 & 2^{k+1} \end{pmatrix} = \begin{pmatrix} 2^{k+1} & (k+1)2^k \\ 0 & 2^{k+1} \end{pmatrix} \).