;;;; BEG of file "b2.soln.txt" ;;;;
Dear Numbers&Polys Enthusiast-Scholars
Agree to use braces for grouping (not indicating sets), e.g,
b_{n+1} means "b sub n+1".
I'll write this solution in more detail than you needed to write on
the exam. PLEASE GRADE my writing, and let me know (via email) of
improvements/corrections that you see. Bear in mind that I am
limited by the format of simple email. Best Wishes, "Prof. Jonathan"
================================================================
B2: Define a sequence b_0,b_1,b_2, ... of integers
1: b_0 := 0 and b_1 := 3 and
2: b_{n+2} := 7·b_{n+1} - 10·b_n
for n=0,1, ... .
Use strong induction to prove, for all k >= 0, that
3(k): b_k = 5^k - 2^k .
/------------------------------------------------------------\
/ \
Proof: For k=0,1,... define R(k) := 5^k - 2^k .
Base Cases: Observe that
b_0 = 0 , by definition,
= 1 - 1
= 5^0 - 2^0
= R(0) , again by defn.
Similarly
b_1 = 3 , by defn,
= 5^1 - 2^1
= R(1) , by defn.
================================================================
Induction case:
Fixing a natnum n, our goal is to establish that b_{n+2} equals R(n+2)
using that (3(k)) holds for all k=0,1,2,...,n+1. Here goes! By defn,
b_{n+2} = 7·b_{n+1} - 10·b_n .
Courtesy equalities (3(n+1)) and (3(n)),
4: b_{n+2} = 7·[5^{n+1} - 2^{n+1}] - 10·[5^n - 2^n] .
[That was the "strong induction" step.] Regrouping terms produces
7·[5^{n+1} - 2^{n+1}] = 7·5 · 5^n - 7·2 · 2^n and
10·[5^n - 2^n] = 10 · 5^n - 10 · 2^n .
Gathering the powers of 5 in the righthand sides above thus yields
[7·5 - 10] · 5^n = [35-10] · 5^n = 25 · 5^n .
Similarly, gathering the powers of 2 above gives us
[7·2 - 10] · 2^n = [14-10] · 2^n = 4 · 2^n .
So these together with (4) say that
4': b_{n+2} = 5^2 · 5^n - 2^2 · 2^n
Happily, this last equals R(n+2), which is a comfort. QED
\ /
\____________________________________________________________/
;;;; END of file "b2.soln.txt" ;;;;