2 Consider the following form of induction. strong induction: To prove P(n) is true for every natural number n, prove that for any natural number m, if P(i) is true for all i < m, then P(m) must also be true. Prove using strong induction that the property P(n) defined as if n 1 then there exist prime numbers p1; · · ·; pk with n = p1 ∗ p2 ∗ · · · ∗ pk. holds for all n.
3 Prove that induction implies strong induction and vice-versa.
4 Let us define a tree as follows: • leaf is a tree • if t1 and t2 are trees then node (t1,t2) is a tree • nothing else is a tree Define by recursion the following function rank (height, depth): rank(leaf) = 1 rank(node(t1,t2)) = max(rank(t1),rank(t2))+1 Using induction on the rank, prove that the number of leaves of any binary tree is at most one plus the number of internal nodes. Prove the same by using structural induction.
5 Given the following inductive definition of an expression: • 0 is an expression • 2 is an expression • if e1 and e2 are expressions then e1+e2 and e1*e2 are expressions • nothing else is an expression where + is interpreted as addition and * as multiplication. Prove by structural induction that the value of every expression produced by this grammar is an even number.
