Question

Докажите с помощью математической индукции, что 3^n+1 + 4^2n-1 делится на 13 для любого натурального n.

Answer 1

1) Базис индукции: $n=1$

$3^{1+1}+4^{2\cdot 1-1}=9+4=13~~\vdots ~~13$

2) Предположим что для $n=k$ выполняется кратность

$\left(3^{k+1}+4^{2k-1}\right)~\vdots~~13$

3) Индукционный переход: $n=k+1$

$3^{k+1+1}+4^{2(k+1)-1}=3\cdot 3^{k+1}+16\cdot 4^{2k-1}=3\left(3^{k+1}+4^{2k-1}\right)+13\cdot 4^{2k-1}$

Первое слагаемое делится на 13 по предположению (второй пункт), а второе слагаемое тоже делится на 13 (содержит сомножитель 13), следовательно, $\left(3^{n+1}+4^{2n-1}\right)~\vdots~~13$ для всех $n \in \mathbb{N}$.

Answer 2

Давайте воспользуемся математической индукцией, чтобы доказать, что выражение $3^{n+1} + 4^{2n-1}$ делится на 13 для любого натурального числа $n$.

Шаг базы индукции: При $n = 1$, у нас есть: $3^{1+1} + 4^{2\cdot1-1} = 3^2 + 4^1 = 9 + 4 = 13$. Это число делится на 13, следовательно, база индукции выполняется.

Шаг предположения: Предположим, что для некоторого положительного целого числа $k$ выражение $3^{k+1} + 4^{2k-1}$ делится на 13, то есть делится без остатка.

Шаг индукции: Мы хотим доказать, что если предположение выполняется для $k$, то оно также выполняется для $k+1$.

Рассмотрим выражение $3^{(k+1)+1} + 4^{2(k+1)-1}$: $3^{k+2} + 4^{2k+1}$.

Мы можем записать $3^{k+2}$ как $3 \cdot 3^{k+1}$ и $4^{2k+1}$ как $4 \cdot 4^{2k}$, получаем: $3 \cdot 3^{k+1} + 4 \cdot 4^{2k}$.

Заметим, что $3^{k+1}$ делится на 13 в соответствии с предположением индукции, и также $4^{2k}$ делится на 13, так как $4^{2k} = (4^2)^k = 16^k$, а 16 делится на 13 (16 = 13 + 3). То есть $3 \cdot 3^{k+1}$ и $4 \cdot 4^{2k}$ также делятся на 13.

Таким образом, сумма $3 \cdot 3^{k+1} + 4 \cdot 4^{2k}$ также будет делиться на 13.

Мы показали, что если предположение выполняется для $k$, то оно выполняется и для $k+1$.

Следовательно, по принципу математической индукции, мы доказали, что выражение $3^{n+1} + 4^{2n-1}$ делится на 13 для любого натурального числа $n$.