The function F: Z+Z+ is defined recursively as follows: F(1) =1, F(2)=2, and F(n) = F...

  

Transcribed Image Text:

The function F: Z+Z+ is defined recursively as follows: F(1) =1, F(2)=2, and F(n) = F ([]) + F ([]) -1 for n 3. (i) Calculate the value of F(9). (ii) Use strong induction to prove that F(n) n for every positive integer n. (Suggestion: Recall the inequalities for floor and ceiling functions in Table 1 in Section 2.3.) C.2. A set S of bit strings is defined recursively as follows. Basis step: A S. Recursive step: If w S, then wl S, w01 S, and w10 S. (i) Show that 0111001 S. (ii) For a string w, let P(w) be the statement "The number of 0's in wis less than or equal to the number of 1's in w." Use structural induction to prove that P(w) is true for every string w in S. (iii) Find an example of a string v such that P(v) is true and v S. Explain how you know that your example is not in S. C.3. You have an unlimited supply of blocks of heights 1, 2, and 4 centime tres. You can construct a tower by piling blocks on top of one another. For each positive integer n, let T be the number of different ways to build a tower of height n cm. (E.g. a tower of height of height 3 cm could be made with three 1-cm blocks, or a 1 cm block on top of a 2-cm block, or a 2-cm block on top of a 1-cm block; thus T3 = 3.) Note that the order of blocks matters when we count all the different ways. (i) Find a recurrence relation for the sequence T. Also state the initial conditions. (ii) Use the results of part (i) to calculate the number of different ways to build a tower of height 8 cm. The function F: Z+Z+ is defined recursively as follows: F(1) =1, F(2)=2, and F(n) = F ([]) + F ([]) -1 for n 3. (i) Calculate the value of F(9). (ii) Use strong induction to prove that F(n) n for every positive integer n. (Suggestion: Recall the inequalities for floor and ceiling functions in Table 1 in Section 2.3.) C.2. A set S of bit strings is defined recursively as follows. Basis step: A S. Recursive step: If w S, then wl S, w01 S, and w10 S. (i) Show that 0111001 S. (ii) For a string w, let P(w) be the statement "The number of 0's in wis less than or equal to the number of 1's in w." Use structural induction to prove that P(w) is true for every string w in S. (iii) Find an example of a string v such that P(v) is true and v S. Explain how you know that your example is not in S. C.3. You have an unlimited supply of blocks of heights 1, 2, and 4 centime tres. You can construct a tower by piling blocks on top of one another. For each positive integer n, let T be the number of different ways to build a tower of height n cm. (E.g. a tower of height of height 3 cm could be made with three 1-cm blocks, or a 1 cm block on top of a 2-cm block, or a 2-cm block on top of a 1-cm block; thus T3 = 3.) Note that the order of blocks matters when we count all the different ways. (i) Find a recurrence relation for the sequence T. Also state the initial conditions. (ii) Use the results of part (i) to calculate the number of different ways to build a tower of height 8 cm.