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