MAT 311

11/5/2017 Week 6 Homework

https://www.webassign.net/web/Student/Assignment-Responses/last?dep=17268349 1/9

Current Score : 27 / 30

1. 3/3 points | Previous AnswersHunterDM2 3.1.004a.

The Lucas numbers L(n) have almost the same definition as the Fibonacci numbers:

How is the definition of L(n) different from the definition of F(n) in Definition 3.1?

Week 6 Homework (Homework) WebAssign

L(n) = 1 if n = 1 3 if n = 2 L(n − 1) + L(n − 2) if n > 2.

Subtraction is involved.

Only one previous term is required for the calculation of a new term.

More than 2 previous terms are required in the calculation of a new term.

The base cases are different.

The odd terms are different.

11/5/2017 Week 6 Homework

https://www.webassign.net/web/Student/Assignment-Responses/last?dep=17268349 2/9

2. 3/3 points | Previous AnswersHunterDM2 3.1.006.

Consider the following recurrence relation.

Use this recurrence relation to compute P(1), P(2), P(3), and P(4).

3. 3/3 points | Previous AnswersHunterDM2 3.1.008.

Given the following definition, compute Q(5).

4. 3/3 points | Previous AnswersHunterDM2 3.1.020.

Give a recurrence relation that describes the sequence 3, 9, 27, 81, 243, 729, 2187, ....

P(n) = 0 if n = 0 [P(n − 1)]2 − n if n > 0

P(1) = -1

P(2) = -1

P(3) = -2

P(4) = 0

Q(n) =

0 if n = 0 2 if n = 1 4 if n = 2 Q(n − 1) + Q(n − 2) + Q(n − 3) if n > 2

Q(5) = 22

P(n) = 3 if n = 1 3 · P(n − 1) if n > 1

11/5/2017 Week 6 Homework

https://www.webassign.net/web/Student/Assignment-Responses/last?dep=17268349 3/9

5. 3/3 points | Previous AnswersHunterDM2 3.1.018.

The ancient Indian game of Chaturanga—from which the modern game of chess was apparently derived—was played on a board with 64 squares. A certain folktale tells the story of a Raja who promised a reward of one grain of rice on the first square of the board, two grains on the second square, four on the third, and so on, doubling the number of grains on each successive square.

(a) Write a recurrence relation for R(n), the number of grains of rice on the nth square.

(b) Compute R(64).

9223372036854775808

Assuming a grain of rice weighs 23 milligrams, how many kilograms of rice must be placed on the 64th square? (Round your answer to one decimal place.)

R(n) = 1 if n = 1 2 · R(n − 1) if n > 1

2.1 × 1014 kg

11/5/2017 Week 6 Homework

https://www.webassign.net/web/Student/Assignment-Responses/last?dep=17268349 4/9

6. 3/3 points | Previous AnswersHunterDM2 3.2.012.

Find a polynomial function f(n) such that f(1), f(2), ... , f(8) is the following sequence.

3, 8, 13, 18, 23, 28, 33, 38 f(n) =

5n−2

11/5/2017 Week 6 Homework

https://www.webassign.net/web/Student/Assignment-Responses/last?dep=17268349 5/9

7. 3/3 points | Previous AnswersHunterDM2 3.2.006.

Consider the following recurrence relation.

Prove by induction that for all n ≥ 0.

(Induction on n.) Let Base Case: If the recurrence relation says that and

the formula says that so they match. Inductive Hypothesis: Suppose as inductive hypothesis that

for some Inductive Step: Using the recurrence relation,

Q(n) = 4 if n = 0 2 · Q(n − 1) − 3 if n > 0

Q(n) = 2n + 3,

f(n) = 2n + 3.

n = 0, Q(0) = 4,

f(0) = 2 + 3 = 4 , 0

Q(k − 1) =

2k−1+3

k > 0.

11/5/2017 Week 6 Homework

https://www.webassign.net/web/Student/Assignment-Responses/last?dep=17268349 6/9

so, by induction, for all

Q(k) = 2 · Q(k − 1) − 3, by the second part of the recurrence relation

=

2

2k−1+3

− 3, by inductive hypothesis

= (2k + 6) − 3

= 2k+3

Q(n) = f(n) n ≥ 0.

11/5/2017 Week 6 Homework

https://www.webassign.net/web/Student/Assignment-Responses/last?dep=17268349 7/9

8. 3/3 points | Previous AnswersHunterDM2 3.1.002.

In Fibonacci's model, rabbits live forever. The following modification of Definition 3.1 accounts for dying rabbits:

(a) Compute G(n) for n = 1, 2, ... , 12.

(b) In this modified model, how long do rabbits live? 8 months

G(n) = 0 if n ≤ 0 1 if n = 1 or n = 2 G(n − 1) + G(n − 2) − G(n − 8) if n > 2.

G(1) = 1

G(2) = 1

G(3) = 2

G(4) = 3

G(5) = 5

G(6) = 8

G(7) = 13

G(8) = 21

G(9) = 33

G(10) = 53

G(11) = 84

G(12) = 134

11/5/2017 Week 6 Homework

https://www.webassign.net/web/Student/Assignment-Responses/last?dep=17268349 8/9

9. 0/3 points | Previous AnswersHunterDM2 3.1.012.

If you have ever tried making patterns with a collection of coins, you have probably noticed that you can make hexagons in a natural way by packing circles as tightly as possible. The figure below shows how 19 circles fit into a hexagonal shape with 3 circles on each edge. Let be the number of circles you need to form a hexagon with n circles on each edge. From the figure below, it is clear that and

It can be shown that increasing the number of circles on each edge gives the following recurrence relation:

Calculate 119

H(n)

H(2) = 7 H(3) = 19.

H(n) = 1 if n = 1 H(n − 1) + 6n − 6 if n > 1.

H(6).

11/5/2017 Week 6 Homework

https://www.webassign.net/web/Student/Assignment-Responses/last?dep=17268349 9/9

10.3/3 points | Previous AnswersHunterDM2 3.1.010.

Every year, Alice gets a raise of $1,000 plus 5% of her previous year's salary. Her starting salary is $50,000. Give a recurrence relation for S(n), Alice's salary after n years, for n ≥ 0.

S(n) = 50000 if n = 0 1000 + 1.05 · S(n − 1) if n > 0