===========================================================================
CSC 236 Tutorial Solutions for Week 2 Winter 2012
===========================================================================
1. Make a conjecture about the amounts of postage that can be made exactly
using only 3c and 5c stamps, then prove your conjecture by *complete*
induction.
Q: Conjecture?
A: Every amount of 8c or more can be made exactly.
{ Make sure to write down a table of values, starting with 0, and
to write down for each value whether or not it can be made. When
you get to 11, make sure to ask the students for their intuition
of what's going on: by analogy with the problem from lecture, you
should have some students say that every amount greater than 10
will work, because the three consecutive amounts 8c, 9c, 10c can
all be made, and we can just keep adding 3c stamps to get
everything thereafter. }
0. Define P(n) as: "-] a, -] b, 3a + 5b = n", and prove P(n) by
complete induction on n >= 8.
{ Many different structures can be used to prove this. To "push"
the students in the direction of the proof below, ask them to
think of a way to "adjust" the structure of their proof to match
the intuition they expressed above. If they don't see what
you're getting at, then you might have to show them more of the
proof below, instead of letting them come up with it. }
2. Ind. Hyp.: Suppose n >= 8 and that P(8), ..., P(n-1).
3. Ind. Step: Prove P(n).
Either n = 8 or n = 9 or n = 10 or n >= 11.
Case 1: If n = 8, then n = 8 = 1*3 + 1*5, so P(8).
Case 2: If n = 9, then n = 9 = 3*3 + 0*5, so P(9).
Case 3: If n = 10, then n = 10 = 0*3 + 2*5, so P(10).
Case 4: If n >= 11, then n-3 >= 8 so let a' and b' be such that
n-3 = 3 a' + 5 b', by the I.H..
Then,
n = 3 + (n - 3)
= 3 + 3 a' + 5 b'
= 3 (a' + 1) + 5 b'
so P(n) (by picking a = a'+1, b = b').
4. Conclusion: By complete induction, \-/ n >= 8, P(n).
{ Once you're done, take a minute to ask if anyone would like to
explore other proof structures for this statement. Someone is likely
to suggest using simple induction and breaking it up into cases,
where you can use the facts that 3+3 = 5+1 and 5+5 = 3+3+3+1 to go
from n to n+1, depending on the value of n. If you take the time to
write this down, you get a fairly different-looking proof from the
one above. Its intuition is also fairly different, so some students
may find it easier, or harder, to grasp. Point this out to them. }
2. Let E be the following set of "algebraic expressions":
- x, y, z (- E,
- for all e_1, e_2 (- E, (e_1 + e_2), (e_1 - e_2), and (e_1 * e_2)
also belong to E-- note that these are *unevaluated* expressions,
- E contains nothing else.
For any expression e (- E, let vr(e) denote the number of variable
occurrences in e, and op(e) denote the number of operator occurrences
in e. For example, vr(((x + x) + y)) = 3-- each separate occurrence of
x counts --and op(((x + x) + y)) = 2.
Prove that \-/ e (- E, vr(e) = op(e) + 1.
Use structural induction over E.
Q: What does "structural induction" mean again?
A: Start with the simplest elements in E, and show that each element
that is more complex satisfies the property, under the assumption
that the element(s) it is built from also satisfy the property. In
other words, structure the proof to mirror the recursive structure
of the set.
0. P(e) is the statement: vr(e) = op(e) + 1.
(Note that P is a predicate about one element of E: when doing
structural induction, we work directly with the elements of the
set we are doing induction on.)
1. Base Case: Prove P(e), where e is a "basic" element of E:
either e = x, or e = y, or e = z.
In each case, vr(e) = 1 = 0 + 1 = op(e) + 1, so P(e) holds.
2. Ind. Hyp.: Assume e_1, e_2 (- E and P(e_1) and P(e_2).
(From the recursive definition of E.)
3. Ind. Step: Prove P(e), where e is an element defined recursively
from e_1 and e_2: either e = (e_1 + e_2), or e = (e_1 - e_2), or
e = (e_1 * e_2).
In each case, vr(e) = vr(e_1) + vr(e_2) and
op(e) = op(e_1) + op(e_2) + 1.
Hence, vr(e) = vr(e_1) + vr(e_2)
= (op(e_1) + 1) + (op(e_2) + 1) [by I.H.]
= (op(e_1) + op(e_2) + 1) + 1
= op(e) + 1.
4. Conclusion: By structural induction on E, \-/ e (- E, P(e).
3. Give a recursive definition for each set below.
{ There are potentially many different ways to do these. }
(a) { x (- Z : x is even } # the set of all even integers
- 0 (- E,
- for all x (- E, x + 2 (- E and x - 2 (- E,
- nothing else belongs to E.
Q: Are we done?
A: Technically, yes. Except we should really check that our
answer makes sense.
Q: What does that mean?
A: Our recursive definition must satisfy two properties:
i. Every element in E is an even integer.
ii. Every even integer belongs to E.
i. - 0 is an even integer,
- if x is an even integer, then x + 2 and x - 2 are even.
ii. This is more complicated than it seems: in order to prove
something for every even integer, we need to use a form of
induction. But in order to use induction, we need to have
a recursive definition of the set of even integers. But
that's what we're trying to show is correct!
The solution is to do induction on another set whose
recursive structure we already know is correct, e.g., N.
Then find a relationship between our set and N. In this
case,
{ x (- Z : x is even } = { x (- Z : -] y (- Z, x = 2y }
= { x (- Z : -] y (- N, x = 2y \/ x = -2y }
Then, use simple induction to show that
\-/ y (- N, 2y (- E /\ -2y (- E
- 2 * 0 = -2 * 0 = 0 (- E,
- for any y, if 2y (- E and -2y (- E, then
2(y+1) = 2y + 2 (- E and -2(y+1) = -2y - 2 (- E.
(b) { n (- N : -] k (- N, n = 10^k } # the set of all powers of 10
- 1 (- T,
- for all x (- T, 10 x (- T,
- nothing lese belongs to T.
Q: Does this definition work?
A: (See part(a) above.)
i. Every element of T is a power of 10:
- 1 = 10^0,
- if x = 10^k for some k, then 10 x = 10^{k+1}.
ii. Every power of 10 belongs to T:
By simple induction on k, show that 10^k belongs to T:
- 10^0 = 1 (- T,
- for any k, if 10^k (- T, then so does
10^{k+1} = 10 * 10^k.