Starting from:

$29.99

ASSIGNMENT-3 CS 2214: DISCRETE STRUCTURES FOR COMPUTING

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

More products