You are writing a proof by mathematical induction that n j

You are writing a proof by mathematical induction that n j = 1 (6j) = 3n^2 +3n is true for all integers n > 0. For the base case, we check that 6 = 3 (12)+3(1). For the induction part of this proof, you make an assumption (the inductive hypothesis) about a number k, then have a statement you wish to prove. Write down this \"proof aim\"

Solution

Ans-

Use mathematical induction to show that given a set of n + 1 positive integers, none exceeding 2n, there is at least one integer in this set that divides another integer in the set. Let P(n) be the following propositional function: given a set of n + 1 positive integers, none exceeding 2n, there is at least one integer in this set that divides another integer in the set. The proposition P(1) is true because there is only one set of 1 + 1 positive integers none exceeding 2 · 1. This set is {1, 2} and it contains an integer, namely 1, that divides the other integer, namely 2. This verifies the basis step in our proof by mathematical induction. For the inductive step we assume that P(k) is true for some positive integer k. To prove P(k + 1), we consider a set S of k + 2 positive 3 integers none exceeding 2k + 2. If S {2k + 1, 2k + 2} has cardinality 0 or 1 then we apply the induction hypothesis to S\\{2k + 1, 2k + 2} to conclude that this set contains a dividing pair of integers. Hence we are left with the case that 2k + 1 and 2k + 2 are both in S and S\\{2k + 1, 2k + 2} consists of k positive integers of size at most 2k that pairwise don’t divide each other. If k + 1 is in S then we are done because k + 1 divides 2k + 2. Suppose therefore that k + 1 6 S. Then we replace S by the set S 0 = (S\\{2k + 2}) {k + 1}. The new set S 0 is covered by the previous case, so it contains a divisible pair. If that pair does not involve k + 1 then it is also in S. If it involves k + 1 then this means that some l S\\{k + 1} divides l. That l must also divide 2k + 2 and hence S contains a divisible pair. This completes the inductive step and hence the proof.