Lewati ke konten utama

Indeks Sblm Naik Lnjt

\(\newcommand{\set}[1]{\{#1\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\text{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\ds}{\displaystyle} \newcommand{\mbf}[1]{\mathbf{#1}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)

Subbab 3.6 Induksi Matematika

Sekarang kita beralih ke induksi, pasangan rekursi yang sama kuatnya.

Misalkan \(n\) bilangan bulat positif. Perhatikan pernyataan-pernyataan matematika berikut, yang masing-masing melibatkan \(n\text{:}\)

\(2n+7 = 13\text{.}\)
\(3n-5=9\text{.}\)
\(n^2-5n+9=3\text{.}\)
\(8n-3 \lt 48\text{.}\)
\(8n-3 > 0\text{.}\)
\((n+3)(n+2) =n^2+5n+6\text{.}\)
\(n^2 -6n + 13 \ge 0\text{.}\)

Pernyataan semacam itu disebut pernyataan terbuka. Pernyataan terbuka dapat dipandang sebagai kondisi, i.e., pernyataan yang berlaku untuk nilai-nilai \(n\) tertentu. Pernyataan 1 hanya berlaku ketika \(n=3\text{.}\) Pernyataan 2 tidak pernah berlaku, i.e., pernyataan itu tidak memiliki solusi dalam bilangan bulat positif. Pernyataan 3 memiliki tepat dua solusi, sedangkan Pernyataan 4 memiliki enam solusi. Sebaliknya, Pernyataan 5, 6, dan 7 berlaku untuk semua bilangan bulat positif.

Pada tahap ini, Anda mungkin menggaruk kepala sambil menganggap pembahasan ini terlalu sederhana. Namun, mari kita perhatikan beberapa pernyataan yang sedikit lebih rumit.

Jumlah \(n\) bilangan bulat positif pertama adalah \(n(n+1)/2\text{.}\)
Jumlah \(n\) bilangan bulat positif ganjil pertama adalah \(n^2\text{.}\)
\(n^n \ge n! + 4,000,000,000n\,2^n\) ketika \(n\ge 14\text{.}\)

Bagaimana kita dapat membuktikan kebenaran pernyataan-pernyataan semacam itu, tentu dengan syarat bahwa pernyataannya memang benar? Titik awal untuk menjawabnya adalah prinsip berikut:

Prinsip 3.11. Prinsip Induksi Matematika.

Misalkan \(S_n\) suatu pernyataan terbuka yang melibatkan bilangan bulat positif \(n\text{.}\) Jika \(S_1\) benar dan, untuk setiap bilangan bulat positif \(k\text{,}\) asumsi bahwa pernyataan \(S_k\) benar mengakibatkan pernyataan \(S_{k+1}\) benar, maka \(S_n\) benar untuk setiap bilangan bulat positif \(n\text{.}\)

Dengan sedikit pemikiran, Anda akan melihat bahwa Prinsip Induksi Matematika ekuivalen secara logis dengan Sifat Terurut Baik pada Bilangan Bulat Positif. Jika belum melakukannya, sekarang mungkin waktu yang tepat untuk meninjau materi latar belakang dalam Lampiran B.

Sblm Ke Atas Lnjt