Recitation 6 4 Problem: The power of 3 Let n be a number whose decimal expansion consists of 3" identical digits. Show b induction that 3"N. For example 32|777 Recall that 3 divides a number iff it divides the sum of its digits Solution. We proceed by induction on n. Let P(n) be the proposition that 3n| M where the decimal expansion of N consists of 3" identical digits Base case. P(O)is true because 3=1 divides every number Inductive step. Now we show that, for all n20, P(n) implies P(n+1). Fix any n 20 and assume P(n)is true. Consider a number whose decimal expansion consists of 3 n+i copies aaaaaa aad:: aag:y aaaaaa. aag 1000...001000..001 Now 3 divides the first term by the assumption P(n), and 3 divides the second term since the digits sum to 3. Therefore, the whole expression is divisible by 3"+. This proves P(n+1) By the principle of induction P(n)is true for all n>0� �� Recitation 6 6 4 Problem: The power of 3. Let N be a number whose decimal expansion consists of 3n identical digits. Show by induction that 3n | N. For example: 32 777777777� | 32 = 9 digits Recall that 3 divides a number iff it divides the sum of its digits. Solution. We proceed by induction on n. Let P(n) be the proposition that 3n | N, where the decimal expansion of N consists of 3n identical digits. Base case. P(0) is true because 30 = 1 divides every number. Inductive step. Now we show that, for all n ≥ 0, P(n) implies P(n + 1). Fix any n ≥ 0 and assume P(n) is true. Consider a number whose decimal expansion consists of 3n+1 copies of the digit a: aaaaaa . . . aaaaaa = aaa . . . aaa aaa . . . aaa aaa . . . aaa � �� � � �� � � �� � � �� � 3n+1 digits 3n digits 3n digits 3n digits = aaa . . . aaa 1 000 . . . 001 000 . . . 001 � �� � � · � �� � � �� 3n digits 3n digits 3n digits Now 3n divides the first term by the assumption P(n), and 3 divides the second term since the digits sum to 3. Therefore, the whole expression is divisible by 3n+1. This proves P(n + 1). By the principle of induction P(n) is true for all n ≥ 0