91Ó°ÊÓ

Prove the following statements with either induction, strong induction or proof by smallest counterexample. Prove that \(\sum_{i=1}^{n}(8 i-5)=4 n^{2}-n\) for every positive integer \(n\).

Prove the following statements with either induction, strong induction or proof by smallest counterexample. Concerning the Fibonacci sequence, prove that \(\sum_{k=1}^{n} F_{k}^{2}=F_{n} F_{n+1}\).

Suppose \(n\) (infinitely long) straight lines lie on a plane in such a way that no two of the lines are parallel, and no three of the lines intersect at a single point. Show that this arrangement divides the plane into \(\frac{n^{2}+n+2}{2}\) regions.

Prove that \(3^{1}+3^{2}+3^{3}+3^{4}+\cdots+3^{n}=\frac{3^{n+1}-3}{2}\) for every \(n \in \mathbb{N}\).

Prove that if \(n, k \in \mathbb{N},\) and \(n\) is even and \(k\) is odd, then \(\left(\begin{array}{l}n \\ k\end{array}\right)\) is even.

Prove that if \(n=2^{k}-1\) for some \(k \in \mathbb{N}\), then every entry in the \(n\) th row of Pascal's triangle is odd.

Prove that \(\sum_{k=0}^{p}\left(\begin{array}{c}m \\\ k\end{array}\right)\left(\begin{array}{c}n \\\ p-k\end{array}\right)=\left(\begin{array}{c}m+n \\ p\end{array}\right)\) for non-negative integers \(m, n\) and \(p\). (This equation is from Exercise 7 in Section 3.10 . There we were asked to prove it by combinatorial proof. Here we are asked to prove it with induction.)

Prove: The \(n\) th Fibonacci number \(F_{n}\) is even if and only if \(3 \mid n\).