Find and solve a recurrence relation for the number of ways to stack n poker
chips using red, white and blue chips such that no two red chips are together.
Use your solution to compute the number of ways to stack 15 poker chips.
Solve the following recurrence relations. a. x(n) = x(n − 1) + 3
for n > 1, x(1) = 0 b. x(n) = 5x(n − 1) for n > 1, x(1) = 6
c. x(n) = x(n/5) + 1 for n > 1, x(1) = 1 (solve for n = 5k )
Solve the recurrence equations by Substitution
a) T(n) = 4T (n/2) + n, T (1) = 1
b) T(n) = 4T (n/2) + n2 , T (1) = 1
c) T(n) = 4T (n/2) + n3 , T (1) = 1
a) Find the recurrence relation for the number of ways to
arrange flags on an n foot flagpole with 1 foot high red flags, 2
feet high white flags and 1 foot high blue flags.
b) solve the recurrence relation of part a
Consider the following recurrence relation defined only for n =
2^k for integers k such that k ≥ 1: T(2) = 7, and for n ≥ 4, T(n) =
n + T(n / 2). Three students were working together in a study group
and came up with this answer for this recurrence: T(n) = n * log2
(n) − n − log2 (n) + 8. Determine if this solution is correct by
trying to prove it is correct by induction.
1. Using domain and range transformations, solve the following
recurrence relations:
a) T(1) = 1, T(n) = 2T(n/2) + 6n - 1
b) T(1) = 1, T(n) = 3T(n/2) + n^2 - n