CMSC 250 Homework 8 Answers Fall 2001

1. Base Case:
   	It is true for $n=1$, $11^1-5^1=6$
   	Which is divisible by 6.
   Inductive Hypothesis:
   	$11^k-5^k$ is divisible by six
   Inductive Step:
   Show:
   	$11^{k+1}-5^{k+1}$ is divisible by 6
   Proof:
   	$11^{k+1}-5^{k+1}=11^{k+1} - 11*5^k+11*5^k - 5^{k+1}$
   	$= 11(11^k-5^k) + 5^k(11-5)$
   	$= 11(11^k-5^k) + 5^k*6$
   	the $1^{st}$ term is divisible by 6 by inductive hypothesis and the second term is also divisible by 6 hence the formula holds true.

2. Base Case:
   	for $n=1$ , $2^4-1=16-1=15$, which is divisible by 15.
   Inductive Hypothesis:
   	$15 \vert 2^{4k}-1$ for some integer $k\geq 1$
   Inductive Step:
   Show:
   	15 | $2^{4(k+1)}-1$
   Proof:
   	$2^{4(k+1)}-1 = 2^{4k}*2^4 - 1$
   	$= 2^{4k}*16 - 1$
   	$= 2^{4k}*(15+1) -1$
   	$2^{4k}*15 + (2^{4k}-1)$ QED

3. Base Case:
   	$n=1$, $6^1-2^1=4$ which is divisible by 4
   Inductive Hypothesis:
   	$6^k-2^k$ is divisible by $4$
   Inductive Step:
   Show:
   	$6^{k+1}-2^{k+1}$ is divisible by $4$
   Proof:
   	$6^{k+1}-2^{k+1}=6^{k+1}-6*2^K+6*2^k - 2^{k+1}$
   	$6(6^k-2^k) + 2^k(6-2)$
   	$6(6^k-2^k) + 2^k*4$, QED

4. Base Case:
   	for $n=1$ it is true that $b_1=\sqrt {1!}=\sqrt 1$
   Inductive Hypothesis:
   	$b_k= \sqrt {k!}$
   Inductive Step:
   Show:
   	$b_{k+1}= \sqrt {k+1!}$
   Proof:
   	$b_{k+1}= \sqrt{k+1}*b_k$.
   	$= \sqrt{k+1}* \sqrt {k!}$
   	$= \sqrt{k+1!}$. QED

5. Base Case:
   	$n=1$, $(1+1)2^{1-1} = 2 = 1(2^{1})$
   Inductive Hypothesis:
   	$\sum_{i=1}^{k} (i+1)2^{i-1} = k(2^{k})$.
   Inductive Step:
   Show:
   	$\sum_{i=1}^{k+1} (i+1)2^{i-1} = (k+1)(2^{k+1}).$
   Proof:
   	$\sum_{i=1}^{k+1} (i+1)2^{i-1} = \sum_{i=1}^{k}(i+1)2^{i-1}+(k+2)2^{k}.$
   	$= k(2^{k})+ (k+2)2^{k} = k(2^{k})+k(2^{k})+2(2^{k})$
   	$= 2k(2^{k})+2^{k+1} = k(2^{k+1})+2^{k+1} = (k+1)2^{k+1}.$ QED

6. Base Case:
   	The property holds for $n=1$ and $n=2$.
   	$a_1=2$ and $a_2=6$ and both 2 and 6 are even integers
   Inductive Hypothesis:
   	$a_i$ is even for all integers i with $1\leq i < k$, $k\geq 3$.
   Inductive Step:
   Show:
   	$a_k$ is even
   Proof:
   	$a_{k} = 3a_{k-2}$
   	Since $k\geq 3$, $k-2\geq 1$, so $a_{k-2}$ is even by the IH.
   	Hence, $a_{k-2}=2l$ for some $l\in{\bf {Z}}$.
   	Hence, $a_{k}=3(2l)=2(3l)$, which means that $a_{k}$ is even. QED

7. Base Case:
   	$n=1$ $3\equiv 3\hbox{ mod } 8$. $n=2$, $11\equiv 3\hbox{ mod }8$.
   Inductive Hypothesis:
   	$\forall 1\leq i < k$, $a_{i}\equiv 3\hbox{ mod }8$.
   Inductive Step:
   Show:
   	$a_{k}\equiv 3\hbox{ mod }8$.
   Proof:
   	$a_{k} = 5a_{k-1}+4a_{k-2}$.
   	By the IH, $a_{k-1} = 8l+3$ for some $l\in{\bf {Z}}$, and $a_{k-2} = 8m+3$ for some $m\in{\bf {Z}}$.
   	Hence, $a_{k} = 5(8l+3) + 4(8m+3) = 5(8l) + 4(8m) + 15 + 12$.
   	$= 8(5l) + 8(4m) + 24 + 3 = 8(5l + 4m + 3) + 3$
   	which means that $a_{k}\equiv 3\hbox{ mod }8$. QED

8. Base Case:
   	The inequality holds for $n=1,n=2$ and $n=3$
   	$a_{1} = 2 < 3^{1}$, $a_{2} = 7 < 3^{2}$, $a_{3} = 25 < 3^{3}$.
   Inductive Hypothesis:
   	Suppose $a_i < 3^i$ for all integers i with $1\leq i < k$, for $k\geq 4$.
   Inductive Step:
   Show:
   	$a_{k} < 3^{k}$
   Proof:
   	$a_k=a_{k-1}+a_{k-2}+a_{k-3}$
   	By the IH, $a_{k-1} < 3^{k-1}$, $a_{k-2} < 3^{k-2}$, and $a_{k-3}<3^{k-3}$.
   	Hence, $a_{k} < 3^{k-1} + 3^{k-2} + 3^{k-3} < 3^{k-1} + 3^{k-1} + 3^{k-1} = 3(3^{k-1}) = 3^{k}$. QED

9. Base Case:
   	The formula holds for $a=1,a=2 and a=3$,because 4,8, and 12 are all divisible by 4.
   Inductive Hypothesis:
   	Suppose $4\vert a_i$ for all integers $i$ with $0\leq i < k$ for some $k\geq 4$.
   Inductive Step:
   Show:
   	$4\vert a_k$.
   Proof:
   	$a_{k} = a_{k-1}+a_{k-2} + 6a_{k-3}$.
   	By the IH, $\exists j,l,m\in{\bf {Z}}$ such that $a_{k-1}=4j$, $a_{k-2}=4l$, $a_{k-3}=4m$.
   	Hence $a_{k} = 4j + 4l + 24m = 4(j + l + 6m)$, so $4 \vert a_{k}$. QED

About this document ...

This document was generated using the LaTeX2HTML translator Version 99.1 release (March 30, 1999)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -show_section_numbers -split 0 -no_navigation -no_footnode h8ans.tex

The translation was initiated by Deep Saraf on 2001-10-25