Discrete Mathematics Answers

For the following recursive functions, Prove that a_m,n = m · n. Here a_m,n is defined recursively for (m, n) ∈ N × N.

a_m.n = { 0 if m=0

n+a_m-1,n if m!=0

Let the sequence T_n be defined by T₁ = T₂ = T₃ = 1 and T_n = T_n-1 + T_n-2 + T_n-3 for n ≥ 4. Use induction to prove that T_n < 2ⁿ for n ≥ 4

There is a long line of eager children outside of your house for trick-or-treating, and with good reason! Word has gotten around that you will give out 3^k pieces of candy to the k^th trick-or-treater to arrive. Children love you, dentists despise you.

(a) Expressed in summation notation (using a Σ), what is c_n, the total amount of candy that you should buy to accommodate n children total?

(b) Use induction to prove that the total amount of candy that you need is given by the closed-form solution: c_n = (3ⁿ⁺¹ - 3) / 2 

Let f_n be the n^th Fibonacci number. Prove that, for n > 0 [Hint: use strong induction]:

f_n = 1/√5 [((1+√5)/2)ⁿ - ((1-√5)/2)ⁿ ]

Using mathematical induction, prove that for every positive integer n,

1 · 2 + 2 · 3 + · · · + n(n + 1) = (n(n + 1)(n + 2)) / 3