91Ó°ÊÓ

Suppose \(b_{1}, b_{2}, b_{3}, \ldots\) is a sequence defined as follows: $$ \begin{aligned} &b_{1}=4, b_{2}=12 \\ &b_{k}=b_{k-2}+b_{k-1} \quad \text { for all integers } k \geq 3 . \end{aligned} $$ Prove that \(b_{n}\) is divisible by 4 for all integers \(n \geq 1\).

For each positive integer \(n\), let \(P(n)\) be the formula $$ 1^{2}+2^{2}+\cdots+n^{2}=\frac{n(n+1)(2 n+1)}{6} $$ a. Write \(P(1)\). Is \(P(1)\) true? b. Write \(P(k)\). c. Write \(P(k+1)\). d. In a proof by mathematical induction that the formula holds for all integers \(n \geq 1\), what must be shown in the inductive step?

For each integer \(n\) with \(n \geq 2\), let \(P(n)\) be the formula $$ \sum_{i=1}^{n-1} i(i+1)=\frac{n(n-1)(n+1)}{3} $$ a. Write \(P(2)\). Is \(P(2)\) true? b. Write \(P(k)\). c. Write \(P(k+1)\). d. In a proof by mathematical induction that the formula holds for all integers \(n \geq 2\), what must be shown in the inductive step?

Evaluate the sum \(\sum_{k=1}^{n} \frac{k}{(k+1) !}\) for \(n=1,2,3,4\), and 5 . Make a conjecture about a formula for this sum for general \(n\), and prove your conjecture by mathernatical induction.

The following while loop implements a way to multiply two numbers that was developed by the ancient Egyptians. [Pre-condition: \(A\) and \(B\) are positive integers, \(x=A\), \(y=B\), and product \(=0 .]\) while \((y \neq 0)\) \(r:=y \bmod 2\) if \(r=0\) then do \(x:=2 \cdot x\) \(y:=y \operatorname{div} 2\) end do if \(r=1\) then do product \(:=\) product \(+x\) end do end while [Post-condition: product \(=A \cdot B]\) Prove the correctness of this loop with respect to its pre- and post- conditions by using the loop invariant $$ I(n): \quad " x y+\text { product }=A \cdot B \cdot " $$

Any product of two or more integers is a result of successive multiplications of two integers at a time. For instance, here are a few of the ways in which \(a_{1} a_{2} a_{3} a_{4}\) might be computed: \(\left(a_{1} a_{2}\right)\left(a_{3} a_{4}\right)\) or \(\left.\left(\left(a_{1} a_{2}\right) a_{3}\right) a_{4}\right)\) or \(a_{1}\left(\left(a_{2} a_{3}\right) a_{4}\right)\). Use strong mathematical induction to prove that any product of two or more odd integers is odd.

Find explicit formulas for sequences of the form \(a_{1}, a_{2}, a_{3}, \ldots\) with the initial terms given in \(10-16\). $$ \frac{1}{4}, \frac{2}{9}, \frac{3}{16}, \frac{4}{25}, \frac{5}{36}, \frac{6}{49} $$

Any sum of two or more integers is a result of successive additions of two integers at a time. For instance, here are a few of the ways in which \(a_{1}+a_{2}+a_{3}+a_{4}\) might be computed: \(\left(a_{1}+a_{2}\right)+\left(a_{3}+a_{4}\right)\) or \(\left.\left(\left(a_{1}+a_{2}\right)+a_{3}\right)+a_{4}\right)\) or \(a_{1}+\left(\left(a_{2}+a_{3}\right)+a_{4}\right)\). Use strong mathematical induction to prove that any sum of two or more even integers is even.

Use strong mathematical induction to prove that for any integer \(n \geq 2\), if \(n\) is even, then any sum of \(n\) odd integers is even, and if \(n\) is odd, then any sum of \(n\) odd integers is odd.

Compute \(4^{1}, 4^{2}, 4^{3}, 4^{4}, 4^{5}, 4^{6}, 4^{7}\), and \(4^{8}\). Make a conjecture about the units digit of \(4^{n}\) where \(n\) is a positive integer. Use strong mathematical induction to prove your conjecture.