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
