Reference no: EM13909169

Please state clearly the property you are trying to prove, the method you will use, and the base case(s) and the inductive hypothesis (hypotheses).

Question 1. Prove that

_1≤kΣⁿk² = n(n + 1)(2n + 1)/6

Question 2. Consider the following definitions for f, g : N → N:

f(0) = 0                         g(0) = 1

f(n + 1) = g(n) - 1          g(n + 1) = f (n) + 1

Compute f(1), g(1), f (2), g(2), f (3) and g(3).

Prove that ∀n ∈ N. f(n) = 0∧g(n) = 1.

Question 3. Consider an app that draws "suit" pictures. The simplest pictures one can draw are ♣ and ♠. One could also draw more complicated pictures by adding a to an already existing picture, or by adding a to two already existing pictures. (The app will take care of placing the figures in the screen so you don't need to take care of this.)

(a) Give the inductive definition of the set SPic of pictures;

(b) Define the function black that counts the number of black figures (♣ or ♠) in the picture, and the function red that counts the number of red figures ( or ) in the picture;

(c) Prove by structural induction on the set of pictures that ∀p ∈ SPic. black(p) ≤ 1 + red(p).

Question 4. Let E be an alphabet. Prove that  ∀ x,y ∈ Σ*. |x| + |y| = |xy|.  Justify all steps in the proof.