I'm trying to use induction to prove this. I'm sure it's a simple proof, but I can't seem to get over the first few steps. Any help?
Allow $P(n)=3^n<n!$
Base Case:
$P(7) = 3^7<7! \rightarrow$ True.
Induction:
Assume $P(k) = 3^k<k!$
Now we must prove $P(k+1)$. Here's where I'm lost. If I'm adding a +1 to the exponent on the LHS, where would I add it to the factorial on the RHS?
$\endgroup$ 54 Answers
$\begingroup$The key to induction proofs is finding a way to work your induction hypothesis into the "$k+1$" case.
We want to show $3^{k+1} < (k+1)!$. Since you know $3^k < k!$, we need to keep an eye out for a factor of $3^k$. Let's just start with the lefthand side of the "$k+1$" case and see what we can do. $$ \begin{align*} 3^{k+1} &= 3 \cdot 3^k\\ &< 3 \cdot k! && \text{(inductive hypothesis)}\\ &< (k+1) \cdot k! && \text{(since k > 2)}\\ &= (k+1)! \end{align*} $$
$\endgroup$ $\begingroup$I'm not sure I understand your question. The rest of the comments/answers have interpreted it in one way, but my answer to the question:
Here's where I'm lost. If I'm adding a +1 to the exponent on the LHS, where would I add it to the factorial on the RHS?
Is that the RHS will look like $(k+1)!$. I'm not sure why you might have thought otherwise? Did you think it might be $k! + 1$? Remember that you are inducting on $k$. So wherever you saw a $n$ you'd replace it with $k+1$.
If this was indeed the confusion you had it would be really really worth it to make sure you understand induction better (and maybe even refresh yourself on the definition of a function?). I can write up a loose description of induction that might help you if you want it.
$\endgroup$ $\begingroup$Base case:$$n = 7 \to {3^7} < 7! \to 2187 < 5040\;\;True % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabg2 % da9iaaiEdacqGHsgIRcaaIZaWaaWbaaSqabeaacaaI3aaaaOGaeyiz % ImQaaG4naiaacgcacqGHsgIRcaaIYaGaaGymaiaaiIdacaaI3aGaey % izImQaaGynaiaaicdacaaI0aGaaGimaiaaysW7caaMe8Uaamivaiaa % dkhacaWG1bGaamyzaaaa!4FB5! $$Inductive Assumption: Assume$${3^k} < k!\;\;is\;true\;for\;any\;k \ge 7 % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaG4mamaaCa % aaleqabaGaam4AaaaakiabgsMiJkaadUgacaGGHaGaaGjbVlaaysW7 % caWGPbGaam4CaiaaysW7caWG0bGaamOCaiaadwhacaWGLbGaaGjbVl % aadAgacaWGVbGaamOCaiaaysW7caWGHbGaamOBaiaadMhacaaMe8Ua % am4Aaiabg6da+iaaiEdaaaa!527F! $$Now, we have to show:$$\;{3^{k + 1}} < (k + 1)!\;\;is\;true\;too. % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGjbVlaaio % dadaahaaWcbeqaaiaadUgacqGHRaWkcaaIXaaaaOGaeyizImQaaiik % aiaadUgacqGHRaWkcaaIXaGaaiykaiaacgcacaaMe8UaaGjbVlaadM % gacaWGZbGaaGjbVlaadshacaWGYbGaamyDaiaadwgacaaMe8UaamiD % aiaad+gacaWGVbGaaiOlaaaa!50B2! $$Lets start:$${3^k} < k! \to 3 \times {3^k} < 3 \times k! \to {3^{k + 1}} < 3 \times k!\;\;\;(A) % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaG4mamaaCa % aaleqabaGaam4AaaaakiabgsMiJkaadUgacaGGHaGaeyOKH4QaaG4m % aiabgEna0kaaiodadaahaaWcbeqaaiaadUgaaaGccqGHKjYOcaaIZa % Gaey41aqRaam4AaiaacgcacqGHsgIRcaaIZaWaaWbaaSqabeaacaWG % RbGaey4kaSIaaGymaaaakiabgsMiJkaaiodacqGHxdaTcaWGRbGaai % yiaiaaysW7caaMe8UaaGjbVlaacIcacaWGbbGaaiykaaaa!5A26! $$On the other hand:$$k \ge 7 \to 7 \le k \to 8 \le k + 1 \to 3 < 8 \le k + 1 \to 3 < k + 1\; % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4Aaiabg6 % da+iaaiEdacqGHsgIRcaaI3aGaeyipaWJaam4AaiabgkziUkaaiIda % cqGH8aapcaWGRbGaey4kaSIaaGymaiabgkziUkaaiodacqGH8aapca % aI4aGaeyipaWJaam4AaiabgUcaRiaaigdacqGHsgIRcaaIZaGaeyip % aWJaam4AaiabgUcaRiaaigdacaaMe8oaaa!5347! $$$$ \times k! \to 3 \times k! < (k + 1) \times k!\;\;\;(B) % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaey41aqRaam % 4AaiaacgcacqGHsgIRcaaIZaGaey41aqRaam4AaiaacgcacqGH8aap % caGGOaGaam4AaiabgUcaRiaaigdacaGGPaGaey41aqRaam4Aaiaacg % cacaaMe8UaaGjbVlaaysW7caGGOaGaamOqaiaacMcaaaa!4F42! $$$$A,\;B \to \left\{ {\begin{array}{*{20}{c}}{{3^{k + 1}} < 3 \times k!\quad \;\;\;\;\;\;}\\{3 \times k! < (k + 1) \times k!}\end{array}} \right. \to {3^{k + 1}} < (k + 1) \times k! \to {3^{k + 1}} < (k + 1)! % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyqaiaacY % cacaaMe8UaamOqaiabgkziUoaaceaabaqbaeqabiqaaaqaaiaaioda % daahaaWcbeqaaiaadUgacqGHRaWkcaaIXaaaaOGaeyizImQaaG4mai % abgEna0kaadUgacaGGHaGaaGzbVlaaysW7caaMe8UaaGjbVlaaysW7 % caaMe8UaaGjbVdqaaiaaiodacqGHxdaTcaWGRbGaaiyiaiabgYda8i % aacIcacaWGRbGaey4kaSIaaGymaiaacMcacqGHxdaTcaWGRbGaaiyi % aaaaaiaawUhaaiabgkziUkaaiodadaahaaWcbeqaaiaadUgacqGHRa % WkcaaIXaaaaOGaeyipaWJaaiikaiaadUgacqGHRaWkcaaIXaGaaiyk % aiabgEna0kaadUgacaGGHaGaeyOKH4QaaG4mamaaCaaaleqabaGaam % 4AaiabgUcaRiaaigdaaaGccqGH8aapcaGGOaGaam4AaiabgUcaRiaa % igdacaGGPaGaaiyiaaaa!773C! $$So, we proved:$${3^n} < n!\;\;for\;any\;n \ge 7 % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaG4mamaaCa % aaleqabaGaamOBaaaakiabgsMiJkaad6gacaGGHaGaaGjbVlaaysW7 % caWGMbGaam4BaiaadkhacaaMe8Uaamyyaiaad6gacaWG5bGaaGjbVl % aad6gacqGHLjYScaaI3aaaaa!4A72! $$
$\endgroup$ $\begingroup$Single line:
If $3^k < k!$ and $k>6$ then $3^{k+1} = 3\times 3^k < 3\times k! < (k+1)\times k! = (k+1)!$
(As $n > 6$ we can assume than $k>6$ and therefor $k+1 > 7 > 3$)
=======================================
If I'm adding a +1 to the exponent on the LHS, where would I add it to the factorial on the RHS?
What does "adding a $+1$ to an exponent" mean?
It means multiplying by the base.
So do that.
$3^{k+1} = 3\times 3^k$.
Now if $3^k < k!$ that means $3\times 3^k < 3\times k!$
where would I add it to the factorial on the RHS?
well that means multiplying the factorial by $k+1$.
So $(k+1)! = k! \times (k+1)$.
Now you have to compare $3\times k!$ to $k! \times (k+1)$ and the rest is obvious.
.....
$3\times k! < (k+1)\times k!$ so long as $k + 1 > 3$ or $k > 2$. And as $k > 6$ we have that.
.....
So
$3^{k+1}\color{tan}=$
$\color{red}{3\times 3^k<3\times k! < (k+1)\times k!}$
$\color{tan}= (k+1)!$
$\endgroup$
