1) Для n=1 получаем 8=8 2) Пусть утверждение верно для какого-то n=k, то есть (5^k+2∗3^k−3) кратно 8. Докажем, что и для n=k+1 утверждение верно. Для n=k+1 выражение выглядит как 5*5^k+2∗3*3^k−3=5*(5^k+2∗3^k−3)-4*(3^k-3). (5^k+2∗3^k−3) кратно 8 по предположению индукции. 4*(3^k-3) кратно 4(так как один из множителей кратен 4) и, так как (3^k-3) кратно 2 (3^k - нечетное число, 3 - тоже, разность двух нечетных чисел есть число четное, то есть кратное 2), кратно 8. Сумма двух чисел, кратных 8, также дает число, кратное 8. Доказано.
Добавляя к любой компании, состоящей только из мальчиков, девочку, будем получать компанию с девочкой. Но есть еще компании с девочкой, в которых два мальчика - таких компаний Поэтому компаний с девочкой на 45 больше, чем компаний без девочки.
Замечание. Кто не проходил числа сочетаний, может рассуждать так: одного мальчика можно выбрать после чего второго мальчика можно выбрать При этом мы могли получить пару мальчиков (A,B), а могли - пару (B,A). Поскольку порядок, в котором мы выбирали мальчиков, нас не интересует, множество получившихся пар мы делим на два.
Поэтому компаний с девочкой на 45 больше, чем компаний без девочки.
мы делим на два.
2) Пусть утверждение верно для какого-то n=k, то есть (5^k+2∗3^k−3) кратно 8. Докажем, что и для n=k+1 утверждение верно.
Для n=k+1 выражение выглядит как 5*5^k+2∗3*3^k−3=5*(5^k+2∗3^k−3)-4*(3^k-3).
(5^k+2∗3^k−3) кратно 8 по предположению индукции. 4*(3^k-3) кратно 4(так как один из множителей кратен 4) и, так как (3^k-3) кратно 2 (3^k - нечетное число, 3 - тоже, разность двух нечетных чисел есть число четное, то есть кратное 2), кратно 8. Сумма двух чисел, кратных 8, также дает число, кратное 8.
Доказано.