3.4 Problems

Prove the following statements using mathematical induction.

1. 1.
   ​

   For every integer $n\geqslant 0$, $4^{n}-1$ is divisible by $3$.

2. 2.
   ​

   For every $n\in\mathbb{N}$, $\sum_{k=1}^{n}k^{3}=\frac{1}{4}n^{2}(n+1)^{2}$.

3. 3.
   ​

   Every positive power of 13 can be written as a sum of two squares.

4. 4.
   ​

   H02: Let $A$ be a set with $|A|=n$. Then $|\mathcal{P}(A)|=2^{n}$ for every integer $n\geqslant 0$.

   NOTE: You must prove this by mathematical induction to pass H02.

5. 5.
   ​

   H02 Resit: Let $S$ be an infinite set of sets such that if $A,B\in S$, then $A\cap B\in S$. If $A_{1},\cdots,A_{n}\in S$, then $\bigcap_{i=1}^{n}A_{i}\in S$ for all $n\in\mathbb{N}$.

   NOTE: You must prove this by mathematical induction to pass the H02 Resit.

6. 6.
   ​

   Let $n\in\mathbb{N}$. Take $n$ lines in the plane such that no two lines are parallel and no three lines meet at a single point. Then these lines divide the plane into $\frac{n(n+1)}{2}+1$ regions.

7. 7.
   ​

   Every set $S$ with $|S|\geqslant 12$ can be partitioned into two sets $A$ and $B$ such that $4\Big{|}|A|$ and $5\Big{|}|B|$.