Given the following definition for the nth Fibonnaci number:

fib(0) = 0,

fib(1) = 1,

fib(n) = fib(n - 1) + fib(n - 2) if n > 1.

Calculate fib(4).

Is the following set inductive?

A = {1, 2, 3, 4, 5, …}

Which of the following is a valid postorder traversal of this binary tree?

What is the basis in the inductive definition of S?

S = {a, ab, abb, abbb, …}

Basis: ?

Induction: If x ∈ S, then xb ∈ S.

Does the following inductive definition allow you to construct the set B of all binary trees over any set A?

Basis: < > ∈ B

Induction: If x ∈ A and L, R ∈ B, then tree(L, x, R) ∈ B

For the following inductive definition, start with the basis element and construct five elements in the set.

Basis: 3 ∈ S.

Induction: If x ∈ S, then 2x - 1 ∈ S.

Find the cardinality of the following set:

S = {2, 5, 8, 11, 14, 17, …, 44, 47}

(hint: establish a bijection between S and a set of the form {0, 1, …, n})

The set A* of all strings over a finite alphabet A is countably infinite.

Let A = { (x + 1)² | x ∈ ℕ and 1 ≤ (x + 1)² ≤ 1000}

What is the cardinality of A?

True or False? ℕ x ℕ is a countable set.