inductionnnn (1 Viewer)

[live.fast]

Prove by induction that, for any positive integer, the product of (n+1)(n+2)...(n+n) is always a multiple of 2^n but never a multiple of 2^(n+1)

?

 

[Trebla]

To prove it is always equal to a multple of 2ⁿ:
Test for n = 1
LHS = 1 + 1
= 2
RHS = 2¹
= 1 x 2¹
LHS = RHS => true for n = 1
Assume statement is true for n = k
i.e. (k + 1)(k + 2)(k + 3)........(k + k) = M.2^k (M is an integer)
Required to prove statement is true for n = k + 1
i.e. (k + 1)(k + 2)(k + 3)........(k + k)(k + 1 + k + 1) = N.2^{k + 1} (N is an integer)
LHS = (k + 1)(k + 2)(k + 3)........(k + k)(k + 1 + k + 1)
= M.2^k.(2k + 2) by assumption
= M(k + 1).2^{k + 1}
= N.2^{k + 1} (N = M(k + 1))
= RHS
If it is true for n = k, then it is also true for n = k + 1
Since it is true for n = 1, hence by induction it is true for all integer n

Not sure about this one but to prove it is never a multiple of 2^{n + 1} use a proof by contradiction from the assumption step:
'Assume' it is true for n = k
i.e. (k + 1)(k + 2)(k + 3)........(k + k) = P.2^{k + 1} (P is an integer)
Try to prove it is true for n = k + 1
i.e. (k + 1)(k + 2)(k + 3)........(k + k)(k + 1 + k + 1) = Q.2^{k + 2} (Q is an integer)
LHS = (k + 1)(k + 2)(k + 3)........(k + k)(k + 1 + k + 1)
= P.2^{k + 1}(2k + 2) by "assumption"
= P(k + 1).2^{k + 2}
= Q.2^{k + 2} (Q = P(k + 1))
= RHS
IF it is true for n = k, then it is true for n = k + 1
BUT it is not true for n = 1
LHS = 2
RHS = 2²
= 4
LHS =/= RHS, there it doesn't work for n = 1, hence it won't work for all integers of n (i.e. the assumption has failed)