ASSIGNMENT-3
CS 2214: DISCRETE STRUCTURES FOR COMPUTING
Instructions: Please submit a single pdf file to gradescope.
1. Consider the two systems of linear equations
x
00 = ax0 + by0
y
00 = cx0 + dy0
x
0 = px + qy
y
0 = rx + sy
We may rewrite the above equations as ?
x
00
y
00?
= A
?
x
0
y
0
?
and ?
x
0
y
0
?
= B
?
x
y
?
, where
A =
?
a b
c d?
and B =
?
p q
r s?
are the coefficient matrices. Suppose C is a matrix
such that ?
x
00
y
00?
= C
?
x
y
?
. By substitution show that C = AB.
In summary, matrix multiplication appears naturally via substitution of one set of
linear equations into another.
2. Find a closed form formula for
Xn
k=0
(3k + 1)2 = 12 + 42 + . . . + (3n + 1)2
Hint: Use the formula for Pn
k=1 k
2 and Pn
k=1 k derived in class.
3. Prove that 13 divides 3n+1 + 42n−1
for every positive integer n using induction.
4. Let {Fn}n≥0 denote the Fibonacci sequence. Prove that, if
A =
?
1 1
1 0?
then
A
n =
?
Fn+1 Fn
Fn Fn−1
?
for n ≥ 1 using induction.
1
