Hi Everyone, Post your proofs for the Feb 1 in-class exercise here. Best, Chris

-- Feb 1 In-Class Exercise

We will prove that @BT@n! = O((n/2)^n)@BT@. To show this, we want to find a constant c s.t. @BT@n! <= c*(n/2)^n@BT@. Base case: @BT@n = 2@BT@ @BT@2! <= c*(2/2)^2@BT@ @BT@2! <= c*1^2@BT@, works for @BT@c = 2@BT@. Inductive case: Knowing that @BT@n! <= c*(n/2)^n@BT@, we want to show @BT@(n+1)! <= c*((n+1)/2)^(n+1)@BT@ Break down into: @BT@(n+1) * n! <= c((n+1)/2)^n * c((n+1)/2)@BT@. Divide out the original rule to yield: @BT@n+1 <= c((n+1)/2)@BT@ If c >= 2, the above inequality will be satisfied.

-- Feb 1 In-Class Exercise

Here's my solution; I hope the parentheses are correct Base Case: f(4) = (4/2)^4 = 16 4! = 12 TRUE inductive case: Assume (n/2)^n > n! ((n+1)/2)^(n+1) >= (n+1)! ((n+1)/2)^n * (n+1)/2 >= n! * (n+1) >>Divide by (n+1) ((n+1)/2)^n * 1/2 >= n! By the inductive hypothesis (n/2)^n > n! Therefore if we can prove 1/2*((n+1)/2)^n >= (n/2)^n, we have proved our theorem 1/2*((n+1)/2)^n >= (n/2)^n ((n+1)^n)/(2^(n+1)) >= (n^n)/(2^n) ((n+1)^n)/2 >= (n^n) (n+1)^n >= (n^n)*2 n^n + n*n^(n-1) + K*n^(n-2) >= (n^n)*2 n*n^(n-1) + K*n^(n-2) >= n^n n^n + K*n^(n-2) >= n^n therefore: true

-- Feb 1 In-Class Exercise

Just a comment. If you want to use latex expressions enclose them using backquotes rather than $.

-- Feb 1 In-Class Exercise

((resource:cw1.jpg|Resource Description for cw1.jpg))

-- Feb 1 In-Class Exercise

((resource:19E5397D-988B-4521-B3B5-13B05B79CEEF.jpeg|Resource Description for 19E5397D-988B-4521-B3B5-13B05B79CEEF.jpeg))