## Math2320 Second Quiz Answers to both Versions

1. Find a suitable integer m and then prove by induction that for all n>= m , n!>3^n .

We need to first make a conjecture of what a suitable value for m could be. Make a table of values:

```n       1       2       3       4       5       6       7       8      9
3^n     3       9       27      81      243     729     2187    6861    20583
n!      1       2       6       24      120     720     5040    40320   362880
```

Let us conjecture that m=7 will work and prove it by induction. Clearly we have already done the base step by virtue of the above table. Assume that n is an integer greater than or equal 6, and assume that n!> 3^n. We must prove that (n+1)! > 3^(n+1) and then we are finished.

It is better practice to look at the n+1 case and see how you can use the n case to help you rather than to start with the n case and then see how to manipulate it.

So we wish to show (n+1)! > 3^(n+1):
Well, (n+1)! = (n+1) * n! which, by induction hypothesis, is greater than (n+1) * 3^n, hence (n+1)! > (n+1)*3^n. Now we finish by just observing that since n> 6, we certainly have that (n+1)*3^n > 3 * 3^n = 3^(n+1).

### Version 1

2. Give a nice recursive definition of the function H(n) where the domain of H is the set of all non-negative integers and H(n) is the largest integer m <= n so that the Hexadecimal expansion of m ends with two 0's (i.e. simply m is a multiple of 256).

Read it carefully and realize that we just want that H(n) should be the largest multiple of 256 which is less than or equal to n. How could we define H(n+1) in terms of H defined at smaller values, e.g. H(n)?

One way: H(0)=0,

`   `
H(n+1) is equal to H(n) if, one way to say it, n-H(n) <255
and then if n-H(n)=255, we set H(n+1)=H(n)+256.

Another way: H(0)=H(1)=...=H(255)=0 and for n>255, define H(n)=256+H(n-256).

3. S is the set of bit strings which is recursively defined by the following two rules:
• the empty string lambda is in S ,
• if w in S , then each of w0 , 1w1 and w11 are in S .

For each of the following two statements, state if they are true. If the case that you answer the statement is not true give a counterexample to demonstrate it.

1. Each member of S has an even number of 1's.

True (and quite easy to see by looking at the generation rules).

2. Every string which has an even number of 1's is in S .

False: Imagine an arbitrary string with an even number of 1's. How could it be built by the rules. Refine your imagined string to keep excluding the rules. If the string does not end with 11 then the w11 rule doesn't help. If it doesn't end with a 0, then the w0 rule doesn't help. So we are now thinking of a string that ends with 01 so that neither of those rules helps. The only rule that remains is the 1w1 rule. So what about simply the string 01 - oh wait it doesn't have an even number of 1's. Ok, but if the string starts with a 0, then the 1w1 rule can't help. Summarize, it must end with 01, begin with 0 and have an even number of 1's. 0101 would seem to do it (and many others).

### Other version

Give a nice recursive definition of the following set of positive integers (not strings!)

S= { 2,20,202,2020,20202,202020, ... }.

At first it is tempting to just say something like, if n is in S then so is 10*n+2 or maybe we should have said just 10*n? Or maybe we need a case rule for the generation!

Base: 2 and 20 are in S
Generation: if n and 10*n are in S, then so are both of 10n+2 and 10*(10n+2).

Or, instead, you could have: Base: 2 is in S,
Generation: if n is in S, then
n+2 is in S so long as 10 divides n,
whereas, if 10 does not divide n, then 10*n is in S.

• The function f(n) is defined recursively by the following rules:
• f(0)=f(1)=f(2)=0 ,
• for n>2 , f(n)=1+f(n-3) .
Compute the values: f(9) , f(3001) .

One way or the other you want to see that f is just counting the number of times you can subtract 3. So f(9)=3 and f(3001)=1000.