My brother brought home some prep work on mathematical induction, and I could do most of it fine (it's been awhile), but the last one is giving me fits. Can anyone take a look at number 3 and tell me what they think? I'm not sure how the hint is relevant.
https://docs.google.com/viewer?a=v&pid=gmail&attid=0.1&thid=12707bc1b5d384f9&mt=application%2Fpdf&url=https%3A%2F%2Fmail.google.com%2Fmail%2F%3Fui%3D2%26ik%3D8b7ea1a01c%26view%3Datt%26th%3D12707bc1b5d384f9%26attid%3D0.1%26disp%3Dattd%26realattid%3Df_g649gpop0%26zw&sig=AHIEtbSrPMUNErcMTOQy7BVTHhmQTurvmw
Edit: Solved it. Here is the explanation for anyone who is interested.
First, we prove the base cases, n = 0 and n = 1. Easy. (0 nCr 0) = 1, which is less than or equal to 1, and (3 nCr 1) = 3, which is less than or equal to 27/4.
Now, assuming our bound is true, we need to prove that (3(n + 1) nCr (n + 1)) is less than or equal to (27/4)^(n+1). Expanding out both sides with the nCr formula, we get:
(3n + 3)! / ((n + 1)! (2n + 2)!) <= (27/4)^n * (27/4)
Expanding further, we get
(3n + 3)(3n + 2)(3n + 1)(3n)! / ((n + 1) n! (2n + 2) (2n + 1) (2n)!) <= (27/4)^n * (27/4)
Bringing out all those extra binomials on the left side, we get
((3n + 3)(3n + 2)(3n + 1)) / ((n + 1)(2n + 2)(2n + 1)) * (3n + 3)! / ((n + 1)! (2n + 2)!) <= (27/4)^n * (27/4)
And we notice that without those extra binomials, it's the old (3n nCr n) formula, so
((3n + 3)(3n + 2)(3n + 1)) / ((n + 1)(2n + 2)(2n + 1)) * (3n nCr n) <= (27/4)^n * (27/4)
Now, we're assuming (3n nCr n) < (27/4)^n, so if we can prove that under all circumstances, ((3n + 3)(3n + 2)(3n + 1)) / ((n + 1)(2n + 2)(2n + 1)) is less than or equal to (27/4), our proof by induction is complete. First, let's simplify a bit; we can cancel two of the binomials after factoring out a three:
(3 (3n + 2)(3n + 1)) / ((2n + 2)(2n + 1)) <= 27/4
Divide by 3:
((3n + 2)(3n + 1)) / ((2n + 2)(2n + 1)) <= 27/12
Expand the binomials out:
(9n^2 + 9n + 2) / (4n^2 + 6n + 2) <= 27/12
If we can prove this is true, we're golden. Here's where his hint comes in. Translating it into English, if every coefficient in the numerator is less than or equal to the corresponding coefficient in the denominator times gamma (in this case, 27/12), then the fraction as a whole must be less than or equal to gamma. Well,
9 <= (4 * 27/12) is true,
9 <= (6 * 27/12) is true, and
2 <= (2 * 27/12) is true.
This shows the lemma true, and therefore, that fraction is less than or equal to 27/12, proving the inductive step, and, along with the two base cases demonstrated earlier, proves the upper bound correct under all circumstances.
I didn't really need to type all of this out to GAF, but I needed to for my brother anyway, so I thought I might as well go ahead and post it here. = D
https://docs.google.com/viewer?a=v&pid=gmail&attid=0.1&thid=12707bc1b5d384f9&mt=application%2Fpdf&url=https%3A%2F%2Fmail.google.com%2Fmail%2F%3Fui%3D2%26ik%3D8b7ea1a01c%26view%3Datt%26th%3D12707bc1b5d384f9%26attid%3D0.1%26disp%3Dattd%26realattid%3Df_g649gpop0%26zw&sig=AHIEtbSrPMUNErcMTOQy7BVTHhmQTurvmw
Edit: Solved it. Here is the explanation for anyone who is interested.
First, we prove the base cases, n = 0 and n = 1. Easy. (0 nCr 0) = 1, which is less than or equal to 1, and (3 nCr 1) = 3, which is less than or equal to 27/4.
Now, assuming our bound is true, we need to prove that (3(n + 1) nCr (n + 1)) is less than or equal to (27/4)^(n+1). Expanding out both sides with the nCr formula, we get:
(3n + 3)! / ((n + 1)! (2n + 2)!) <= (27/4)^n * (27/4)
Expanding further, we get
(3n + 3)(3n + 2)(3n + 1)(3n)! / ((n + 1) n! (2n + 2) (2n + 1) (2n)!) <= (27/4)^n * (27/4)
Bringing out all those extra binomials on the left side, we get
((3n + 3)(3n + 2)(3n + 1)) / ((n + 1)(2n + 2)(2n + 1)) * (3n + 3)! / ((n + 1)! (2n + 2)!) <= (27/4)^n * (27/4)
And we notice that without those extra binomials, it's the old (3n nCr n) formula, so
((3n + 3)(3n + 2)(3n + 1)) / ((n + 1)(2n + 2)(2n + 1)) * (3n nCr n) <= (27/4)^n * (27/4)
Now, we're assuming (3n nCr n) < (27/4)^n, so if we can prove that under all circumstances, ((3n + 3)(3n + 2)(3n + 1)) / ((n + 1)(2n + 2)(2n + 1)) is less than or equal to (27/4), our proof by induction is complete. First, let's simplify a bit; we can cancel two of the binomials after factoring out a three:
(3 (3n + 2)(3n + 1)) / ((2n + 2)(2n + 1)) <= 27/4
Divide by 3:
((3n + 2)(3n + 1)) / ((2n + 2)(2n + 1)) <= 27/12
Expand the binomials out:
(9n^2 + 9n + 2) / (4n^2 + 6n + 2) <= 27/12
If we can prove this is true, we're golden. Here's where his hint comes in. Translating it into English, if every coefficient in the numerator is less than or equal to the corresponding coefficient in the denominator times gamma (in this case, 27/12), then the fraction as a whole must be less than or equal to gamma. Well,
9 <= (4 * 27/12) is true,
9 <= (6 * 27/12) is true, and
2 <= (2 * 27/12) is true.
This shows the lemma true, and therefore, that fraction is less than or equal to 27/12, proving the inductive step, and, along with the two base cases demonstrated earlier, proves the upper bound correct under all circumstances.
I didn't really need to type all of this out to GAF, but I needed to for my brother anyway, so I thought I might as well go ahead and post it here. = D