1a. Proof by induction: For every positive integer
n,
1•3•5...(2n-1)=(2n)!/(2n•n!). Please explain what the exclamation
mark means. Thank you for your help!
1b. Proof by induction: For each integer n>=8,
there are nonnegative integers a and b such that n=3a+5b
Prove these scenarios by mathematical induction:
(1) Prove n2 < 2n for all integers
n>4
(2) Prove that a finite set with n elements has 2n
subsets
(3) Prove that every amount of postage of 12 cents or more can
be formed using just 4-cent and 5-cent stamps
Let G be a simple undirected graph with n vertices where n is an
even number. Prove that G contains a triangle if it has at least
(n^2 / 4) + 1 edges using mathematical induction.
Question 2: A bipartite graph with 2n vertices (namely |V1| =
|V2| = n) is d-regular if and only if the degree of every vertex in
V1 ∪ V2 is exactly d. Show that a d-regular bipartite graph always
has a perfect matching (a matching of size n that includes all
vertices).
***Remarks: All the graphs here are without self loops and
parallel or anti-parallel edges. A network is a directed graph with
source s and sink t and capacity...