Question

3. (15 points) Prove the statements by induction. (a) For n e N, 10|(9n+1 + 72n). (b) The formula for a geometric sum: For n e N, a + 1, n an+1 1 Σα? - a 1 j=0 (c) For n e N and n > 3, there exists n distinct positive integers A1, A2, ..., An such that 1 1 1 = + +...+ a1 A2 an

Answer 1

a P(h): 10 l (ght + 72 ) NEIN g!+! g+7- Q1+99 = 130 + 7211 for n=1 do 1011 30 10 l glt! +721 P(1) is true. Now, assume that P(k) is true to 10 1 1966 + + 72%) => KtI g. (9 --- 10 2k 40.72k T 9 (gK+1 +72k) + 40.71 2k ak >> 10 lg. gkti 101 gkt2 + 49x7 +9.7 +40.7 0 1 (k+1)+1 +7 2(k+!) - P(k+1) is true.

Hence By Mathematical induction, Pln) is tree A nEIN, 10 ff nEIN (9) ght! + 72 ) . ant! | at! nEIN b E go a $ qui pin, for nal, alty p į au a ta' =lta (91) P (1) is thee. P(K) is true. Now, assume that KAI a - نو کے jco KtI consider, K+! KtI + 9 -- a Eau 5=o KH K+2 K42 a KHI 4tal a el - a- kt E qu K+1) 71_1 9-1 true. PCK+D induction, Hence, Principle of P (n) is true for all akt | a- then 7=0

Pln): of n distinct positive integens 8.t. as, 92, -- anan n), B NEIN + L + for n=3 - 3 are such that a=3, 92=3, az out tot de = 5 + 5 + § 21 for n=4 az - 4 9 = 2 at 3 ta T + 4 P(3), P4) are true are Now assume P13), P14).-PCR). true. k integers (distinct positive) 군 + I Car + -- I 9k an choose bky = 9k-1 bz=a. bktı biza, ok L + biti St. = 296 laki L + L + I 29k + I akt au zare .+ I akt + ㅗ ak - au = P(KH) is true Hence By mathematical induction (Strong) Pln) is true for all nEIN. forn Elm, n), I n distinct positive integern sot. to the