Scribd
Upload
29 views2 pages

Extra Credit Assignment 1

Uploaded by

Anuj Jha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
29 views2 pages

Extra Credit Assignment 1

Uploaded by

Anuj Jha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Extra credit assignment 1

Paul Hewitt
20 September 2013

Due date: Wednesday, 25 September


Here are two alternate ways to prove Theorem 4.3.1, page 71 of our text
Discrete Mathematics, by Lovász, Pelikán, and Vesztergombi.

1. Define
   
1 1 1
M= , v0 = , and vn = M vn−1 when n > 0.
1 0 0

a. Prove that for all n


 
n Fn+1
vn = M v0 = .
Fn

b. Diagonalize M :
 
−1 q1 0
M = SQS where Q = .
0 q2

(It is part of the problem to determine S, q1 , and q2 .) Conclude


that for all n
M n = SQn S −1 .
c. Use parts a and b to prove Theorem 4.3.1.

1
2. Define ∞
X
F (x) = F n xn .
n=0

a. Prove that
F (x) = x + xF (x) + x2 F (x).
b. Use part a and the method of “partial fractions” to prove that
A B
F (x) = + .
x + q1 x + q2

(It is part of the problem to determine A, B, q1 , and q2 .)


c. Expand the terms in the right-hand side of part b using the geo-
metric series and use this to prove Theorem 4.3.1.

You might also like