CMSC 250 Homework 8 Fall 2001

Due Wed Oct 24 at the beginning of your discussion section.

You must write the solutions to the problems single-sided on your own lined paper, with all sheets stapled together, and with all answers written in sequential order or you will lose points.

Use mathematical induction or strong mathematical induction, as needed, to prove the following for all integers in the specified ranges.

Show that $11^{n}-5^{n}$ is divisible by for all $n\geq 1$ .
Prove that $2^{4n}-1$ is divisible by for all $n\geq 1$ .
Show that for all $n\geq 1$ , $6^{n}-2^{n}$ is divisble by .
Let $b_{1} = 1$ , and $\forall n\geq 2$ , $b_{n} = \sqrt{n}b_{n-1}$ . Show that $\forall n\geq 1$ , $b_{n} = \sqrt{n!}$ .
$\forall n\geq 1,\,\,\sum_{i = 1}^{n} (i + 1)2^{i- 1} = n2^{n}.$
$a_{1}=2$ , $a_{2}=6$ , and $a_{n}=3a_{n-2}\forall n\geq 3$ . Show that $a_{n}$ is even for all $n\geq 1$ .
$a_{1}=3$ , $a_{2}=11$ , and $\forall n\geq 3$ , $a_{n} = 5a_{n-1}+4a_{n-2}$ . Show that $a_{n}\equiv 3\hbox{ mod } 8$ for all $n\geq 3$ .
$a_{1}=2$ , $a_{2}=7$ , $a_{3}=25$ , and $\forall n\geq 3$ , $a_{n} = a_{n-1} + a_{n-2} + a_{n-3}$ . Show that $a_{n} < 3^{n}\,\,\,\forall n\geq 1$ .
Let $a_{1}=4$ , $a_{2}=8$ , $a_{3}=12$ , and $\forall n\geq 4$ , $a_{n}=a_{n-1}+a_{n-2}+6a_{n-3}$ . Prove that $a_{n}$ is divisible by for all $n\geq 1$ .