Question

Weak Induction

(1) Using weak induction, prove that 3" < n! for all integers n > 6.
(2) Prove that log(n!) < n log(n) for all integers n > 1.
Reminder 1: log(1) = 0.
Reminder 2: log(a*b) = log(a) + log (6).
Reminder 3: If a < b then log(a) < log(6).
Note: The base of the logarithms doesn't matter for any of the above.
(3) Prove for all integers n > 1 that if A1, A2, ..., An and B are sets, then:_______.
(A1∩A2∩...∩An)UB = (A1UB)∩(A2UB)∩...∩(AnUB)
Hint: Use the fact that (XNY) UZ = (XUZ)n(Y UZ) where X, Y, and Z are sets.

Answer 1

Following are the answer to this question:

Step-by-step explanation:

In option 1:

The value of n is= 7, which is (base case)

`\to 3^7<7!\\\to 2187<5050\\`

when n=k for the true condition:

`\to 3^k<k!......(i)\\\\`

when n=k+1 it tests the value:

`\to 3^((k+1))= 3^k,3\\\to < (k!) 3 \ substituting \ equation \\\to <k! \cdot (k+1)\\`

since k>6 hence the value is KH>3 hence proved.

In option 2:

when:

for n=1:(base case)

`\log(1!)<=1\log(1)`

0<=0 \\ condition is true

when the above statement holds value n=1

when n=k

`\log(k!) <=k\log(k)....(1)`

when n=k+1

`\log(k+1)!=\log(k!)+\log(k+1)\\`

`<= k \log(k)+\log(kH)\\<= kH\log(kH)\\`

`\because k \log k<=k log(KH)\\\\`
`[\therefore KH>K \Rightarrow \log(KH>\loK)]`

In option 3:

when n=1:

`A_1 \cup B=A_1 \cup B\\\\`

when n=k

`\to (A_1\cap A_2 \cap.....A_k) \cup B\\=(A_1\cup B) \cap(A_2\cup B_2)....(A_k \capB).....(a)\\\to n= k+1\\ \to (A_1\cap A_2 \cap.....A_(kH)) \cup B= (A_1\cup B)\\\\\to [(A_1\cap A_2 \cap.....A_(k)) \cup B]\cap (A_(KH)\cup B)\\\\\to [(A_1\cup B) \cap (A_2 \cup B) \cap (A_3\cup B).....(A_k\cup B)\cap (A_(k+1) \cup B)\\\\ \ \ \ \ \ \ substituting \ equation \ a \\\\`

hence n=k+1 is true.