Assignment #1: induction Solution

The aim of this assignment is to give you some practice with various avours of induction. For each questionbelow you will present a proof by induction. For full marks you need to make it clear to the reader thatthe base case(s) is/are veri ed, that the inductive step follows for each element of the domain (typically the
natural numbers), where the inductive hypothesis is used, and that it is used in a valid case.
Your assignment must be typed to produce a PDF document a1.pdf (hand-written submissions are notacceptable). You may work on the assignment in groups of 1 or 2, and submit a single assignment for theentire group on MarkUs
1. Recall bipartite graphs. Consider the following de nitions:bipartite graph: Undirected graph
V
G = ( V; E ) is bipartite if and only if there exist V 1 ; V 2 such that
= V 1 [ V 2 , V 1 \ V 2 = ; , and every edge in E has one endpoint in V 1 and the other in V 2 .
P(n): Every bipartite graph on
n
vertices has no more than n 2 = 4 edges.
(a) Assume P (234). Can you use this 1 to prove that P (235) follows? Explain why, or why not.
(b) Assume P (235). Can you use this 2 to prove that P (236) follows? Explain why or why not.
(c) Use what you've learned from the previous two answers to construct a proof by simple induction
that: 8 n 2 N ; P ( n ). Note: There are proofs of this claim that are not by simple induction, but
those proofs will receive no marks. Hint: You probably need to strengthen the claim in order
to devise a successful inductive hypothesis. If this seems mysterious, revisit the previous two
answers...
2. De ne function f as follows:
(
( )=
f n
3
if n = 0
2
[ f ( b log 3 n c )] + f ( b log 3 n c ) if n > 0
De ne predicate P ( n ) : \ f ( n ) is a multiple of 4."
(a) Assume P (3). Can you use this 3 to prove P (29)? Explain why or why not.
(b) Assume P (4). Can you use this 4 to prove P (29)? Explain why or why not.
(c) Use complete induction to prove 8 n 2 N ; n > 0 ) P ( n ).
1 If you say yes, P (234) must be a necessary part of your proof.
2 If you say yes, P (235) must be a necessary part of your proof.
3 If you say yes, P (3) must be a necessary part of your proof.
4 If you say yes, P (4) must be a necessary part of your proof.
13. Use the Principle of Well-Ordering to derive a contradiction that proves there are no positive integers
x; y; z such that:
5 x 3 + 50 y 3 = 3 z 3
You may assume, without proof, that if a prime number p divides a perfect cube n 3 , then p also divides
n .
4. De ne T as the smallest set of strings that satis es:
#
#
"*" 2 T
if t 1 ; t 2 2 T then their parenthesized concatenation ( t 1 t 2 ) 2 T .
Some examples: "*", "(**)", "(*(**))" are all in T .
Now read over these four Python functions:
def left_count(s: str) -> int:
"""
Return the number of "(" in s
"""
return s.count("(")
def double_count(s: str) -> int:
"""
Return the number of "((" plus number of "))", including possible
overlaps.
"""
return (len([s[i:] for i in range(len(s)) if s[i:].startswith("((")])
+ len([s[:i] for i in range(len(s) + 1) if s[:i].endswith("))")]))
def left_surplus(s: str, i: int) -> int:
"""
Return the number of "(" minus the number of ")"
in s[:i]
"""
return s.count("(", 0, i) - s.count(")", 0, i)
def max_left_surplus(s: str) -> int:
"""
Return the maximum left surplus for all prefixes of s.
"""
return max([left_surplus(s, i) for i in range(len(s))] + [0])
(a) Use structural induction on T to prove:
8 2T
t
;
left count( t ) # 2 max left surplus( t )
1
(b) Use structural induction on T to prove: [edit:] error fixed September 9
8 2T
t
(
;
double count( t ) =
2
0
left count( t )
1
if t = " # "
otherwise