Reference no: EM132303380

For each induction proof, clearly define the predicate being used, state the universal you are proving, and state the induction principle you are using.

(1) Consider the sequence defined by:

a₁ = 2

a_n = a[_[√n])² + 3a_[√n],n ≥ 2

(a) Write a Python function that takes n ≥ 1 and returns a_n.
(b) Write a Python function that takes n ≥ 2 and returns a_n, but throws an Exception for n < 2. It may not call any helper functions.
(c) Prove that an is divisible by 5 for all n ≥ 2.

(2) Define the function f by:

f(n) = { 10, n = 2

         { 3f ([2n/3]), n ≥ 3

Prove that there is a natural number c such that f(m) ≤ cn⁴ for all natural numbers n ≥ 3.

(3) Let B be the set of binary trees with the following property:

For each non-leaf node in the tree, the heights of the left and right child (where ‘no' child is considered an empty child) differ by 1.

Prove by Induction that if b ∈ B has height h, then the number of nodes in b is at least (1.5)^h - 1.

(4) Let b_h be the number of ordered binary trees (meaning two trees that are mirror images of each other are both counted - which you probably expected anyway) of height h (where we measure height as the number of levels, so an empty tree has height 0). Produce a recursive algebraic formula for b_h, h ∈ N. Justify your result.

(5) Prove by Induction (without using the Binomial Theorem) that

1 - j/k ≤ (1-1/k)^j for all positive j, k ∈ N