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).
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
Another way: H(0)=H(1)=...=H(255)=0 and for n>255, define H(n)=256+H(n-256).
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.
True (and quite easy to see by looking at the generation rules).
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).
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.
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.