Induction Proofs Problem: Choose which answer is correct from the selection of a
ID: 3146828 • Letter: I
Question
Induction Proofs Problem:
Choose which answer is correct from the selection of answers after "[Choose]"
Match each xi with the correct value so that the following induction proof is correct. I suggest that you do the proof yourself on paper first. Trying to do this matching without a written proof in front of you is very frustrating!
Prove that 3n < n! whenever n is an integer greater than 6.
Basis Step
Let n = x1. Then 3x2 = 2187 < x3 = 5040.
Inductive Step
3n+1 = (x6)3n < 3(x7) < (x8)n! = (n+1)!
x1
[ Choose ] 6 (n+1)! n+1 6! n 3 n! 7! 7
x2
[ Choose ] 6 (n+1)! n+1 6! n 3 n! 7! 7
x3
[ Choose ] 6 (n+1)! n+1 6! n 3 n! 7! 7
x4
[ Choose ] 6 (n+1)! n+1 6! n 3 n! 7! 7
x5
[ Choose ] 6 (n+1)! n+1 6! n 3 n! 7! 7
x6
[ Choose ] 6 (n+1)! n+1 6! n 3 n! 7! 7
x7
[ Choose ] 6 (n+1)! n+1 6! n 3 n! 7! 7
x8
[ Choose ] 6 (n+1)! n+1 6! n 3 n! 7! 7
Explanation / Answer
Hi,
Writing down the full proof so that its easy for you to visualize,
every inductive proof has 3 steps
1. Basis step
since given n greater than 6, we choose n=7
LHS 3*7=21
RHS 7! i.e 5040 ie 21<5040, hence true
2. Hypothesis step
assume true for n, i.e 3n<n!
3. inductive step,
we have to prove for n=n+1 using above hypothesis
i.e 3(n+1)<(n+1)!
i.e 3n+3<(n+1)n!
now, you can do the matching easily i,e
x1=7,x2=7,x3=7!, x4=n!,x5=(n+1)!,x6=,x7=(n+1),x8=(n+1)
Thumbs up if this was helpful, otherwise let me know in comments