Seorang siswa mencoba membuktikan bahwa 'Untuk setiap bilangan bulat positif $n$, $3n+2$ adalah bilangan genap' menggunakan induksi matematika.1. Basis Induksi: $P(1): 3(1)+2 = 5$, yang merupakan bilangan ganjil.Siswa tersebut menyadari bahwa basis induksi gagal. Jika siswa tersebut *keliru* berasumsi bahwa $P(1)$ adalah benar dan mencoba melanjutkan ke langkah induksi, apa yang kemungkinan besar akan terjadi?

Langkah induksi juga akan gagal, karena $3(k+1)+2 = (3k+2)+3$. Jika $3k+2$ genap, maka $(3k+2)+3$ akan ganjil.

Barisan Fibonacci didefinisikan sebagai $F_1=1$, $F_2=1$, dan $F_n = F_{n-1} + F_{n-2}$ untuk $n \ge 3$. Kita ingin membuktikan $P(n): F_n < 2^n$ untuk semua bilangan bulat positif $n$.1. Basis Induksi: $P(1): F_1=1 < 2^1=2$ (Benar). $P(2): F_2=1 < 2^2=4$ (Benar).2. Hipotesis Induksi: Asumsikan $P(j)$ benar untuk semua $j$ dengan $1 \le j \le k$, yaitu $F_j < 2^j$.3. Langkah Induksi: Kita perlu menunjukkan $P(k+1)$ benar, yaitu $F_{k+1} < 2^{k+1}$.Bagaimana langkah induksi ini diselesaikan dengan benar?

$F_{k+1} = F_k + F_{k-1}$. Berdasarkan hipotesis induksi, $F_k < 2^k$ dan $F_{k-1} < 2^{k-1}$. Jadi, $F_{k+1} < 2^k + 2^{k-1}$. Untuk $k \ge 2$, $2^{k-1} \le 2^k$, sehingga $2^k + 2^{k-1} \le 2^k + 2^k = 2 \cdot 2^k = 2^{k+1}$.

Bab 1: Induksi Matematika

LATIHAN• 1/5

No. 1

Sebuah barisan $a_n$ didefinisikan secara rekursif sebagai $a_1 = 1$ dan $a_{n+1} = a_n + 2n + 1$ untuk $n ext{ extgreater } 1$ . Jika kita ingin membuktikan bahwa $a_n = n^2$ untuk setiap bilangan asli $n$ menggunakan induksi matematika, apa yang harus menjadi hipotesis induksi yang benar?