PHƯƠNG PHÁP QUY NẠP TOÁN HỌC
I/ LÝ THUYẾT
1/ Để chứng minh một mệnh đề P(n) là đúng với mọi $n\in {{N}^{*}}$ , ta thường dùng phương pháp quy nạp toán học, được tiến hành như sau:
Bước 1 (bước cơ sở): Kiểm tra mệnh đề P(n) đúng với n = 1
Bước 2 (bước quy nạp): Giả thiết mệnh đề P(n) đúng với một số tự nhiên bất kì $n=k,(k\ge 1)$ (ta gọi là giả thiết quy nạp) và chứng minh nó cũng đúng với n = k + 1. Khi đó, theo nguyên lí quy nạp toán học, ta kết luận mệnh đề P(n) đúng với mọi $n\in {{N}^{*}}$
2/ Trong trường hợp phải chứng minh một mệnh đề P(n) là đúng với mọi số tự nhiên $n\ge p$ (p là số tự nhiên) thì:
+ Ở bước 1 ta kiểm tra mệnh đề P(n) đúng với n = p
+ Ở bước 2, ta giả thiết mệnh đề P(n) đúng với một số tự nhiên bất kì n = k,$\left( k\ge p \right)$ và chứng minh rằng nó cũng đúng với n = k + 1
3/ Phép thử với một số hữu hạn số tự nhiên tuy không phải là chứng minh nhưng cho phép ta dự đoán được kết quả. Kết quả này chỉ là giả thiết và để chứng minh ta có thể dùng phương pháp quy nạp toán học
Một số bài toán thường gặp:
+ Chứng minh các mệnh đề toán học liên quan đến lập luận logic
+ Chứng minh các đẳng thức, bất đẳng thức
+ Dự đoán kết quả và chứng minh
II/ VÍ DỤ
VD 1: Chứng minh răng với mọi $n\in {{N}^{*}}$ ta có đẳng thức:
$2+5+8+...+3n-1=\frac{n(3n+1)}{2}$
Giải:
Với n = 1, ta có VT = VP = 2
Vậy hệ thức đúng với n = 1
Giả sử đẳng thức đứng với $n=k\ge 1$ tức là:
$2+5+8+..+3k-1=\frac{k(3k+1)}{2}$
Ta phải chứng minh đẳng thức đúng với n = k + 1, nghĩa là
$2+5+8+...+\left[ 3\left( k+1 \right)-1 \right]=\frac{\left( k+1 \right)\left[ 3\left( k+1 \right)+1 \right]}{2}$
Thật vậy, thừ giả thiết quy nạp, ta có
${{S}_{k+1}}={{S}_{k}}+3k+2=\frac{k(3k+1)}{2}+3k+2=\frac{3{{k}^{2}}+k+6k+4}{2}$
$=\frac{3({{k}^{2}}+2k+1)+k+1}{2}=\frac{(k+1)\left[ 3\left( k+1 \right)+1 \right]}{2}$
Vậy mệnh đề đã được chứng minh.
VD 2: Chứng minh rằng với mọi $n\in {{N}^{*}}$ ta luôn có:
${{n}^{3}}+3{{n}^{2}}+5n$ chia hết cho 3
Giải:
Với n = 1, ta có ${{S}_{1}}=9$ chia hết cho 3
Giả sử với $n=k\ge 1$ , ta có ${{S}_{k}}=({{k}^{3}}+3{{k}^{2}}+5k)$ chia hết cho 3
Ta phải chứng minh rằng ${{S}_{k+1}}$ chia hết cho 3
Thật vậy
${{S}_{k+1}}={{(k+1)}^{3}}+3{{(k+1)}^{2}}+5(k+1)$
$={{k}^{3}}+3{{k}^{2}}+3k+1+3{{k}^{2}}+6k+3+5k+5$
$={{k}^{3}}+3{{k}^{2}}+5k+3{{k}^{2}}+9k+9$
Hay ${{S}_{k+1}}={{S}_{k}}+3({{k}^{2}}+3k+3)$
Theo giả thiết quy nạp thì ${{S}_{k}}$ chia hết cho 3 mặt khác $3({{k}^{2}}+3k+3)$ chia hết cho 3 nên .png)
chia hết cho 3
Vậy với mọi $n\in {{N}^{*}}$ ta có ${{n}^{3}}+3{{n}^{2}}+5n$ chia hết cho 3
VD 3: Chứng minh rằng với mọi số tự nhiên $n\ge 2$ thì ${{3}^{n}}>3n+1$
Giải:
Với n = 2, ta có VT = 8 > 7 = VP
Mệnh đề đúng với n = 2
Giả sử mệnh đề đúng với $n=k\ge 2$ tức là ${{3}^{k}}>3k+1$
Ta cần chứng minh mệnh đề đúng với n = k + 1, nghĩa là
${{3}^{k+1}}>3(k+1)+1$
Thật vậy,
${{3}^{k}}>3k+1\Leftrightarrow {{3}^{k+1}}>9k+3\Leftrightarrow {{3}^{k+1}}>3k+4+6k-1$
Vì $6k-1>0$ nên ${{3}^{k+1}}>3k+4=3(k+1)+1$
Tức là mệnh đề đúng với n = k + 1
Vậy với mọi số tự nhiên $n\ge 2$ thì ${{3}^{n}}>3n+1$
VD 4: Cho tổng ${{S}_{n}}=\frac{1}{1.2}+\frac{1}{2.3}+\frac{1}{3.4}+...+\frac{2}{n(n+1)}$ với mọi $n\in {{N}^{*}}$ . Dự đoán công thức tính tổng ${{S}_{n}}$ và chứng minh bằng quy nạp
Giải:
Ta có:
${{S}_{1}}=\frac{1}{1.2}=\frac{1}{2}$
${{S}_{2}}=\frac{1}{1.2}+\frac{1}{2.3}=\frac{2}{3}$
${{S}_{3}}=\frac{1}{1.2}+\frac{1}{2.3}+\frac{1}{3.4}=\frac{3}{4}$
Ta dự đoán ${{S}_{n}}=\frac{n}{n+1}$ với mọi $n\in {{N}^{*}}$
*Chứng minh:
Với n = 1, ${{S}_{1}}=\frac{1}{2}$ . Mệnh đề đúng với n = 1
Giả sử mệnh đề đúng với $n=k\ge 1$ , tức là
${{S}_{k}}=\frac{1}{1.2}+\frac{1}{2.3}+...+\frac{1}{k(k+1)}=\frac{k}{k+1}$
Ta cần chứng minh mệnh đề đúng với n = k + 1, nghĩa là
${{S}_{k+1}}=\frac{1}{1.2}+\frac{1}{2.3}+...+\frac{1}{(k+1)(k+2)}=\frac{k+1}{k+2}$
Thật vậy, ta có:
${{S}_{k+1}}={{S}_{k}}+\frac{1}{(k+1)(k+2)}=\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}=\frac{{{k}^{2}}+2k+1}{(k+1)(k+2)}=\frac{k+1}{k+2}$
Tức là mệnh đề đúng với n = k + 1
Vậy ${{S}_{n}}=\frac{n}{n+1}$ với mọi $n\in {{N}^{*}}$
VD 5: Chứng minh $\frac{{{a}^{n}}+{{b}^{n}}}{2}\ge {{\left( \frac{a+b}{2} \right)}^{n}}$ với: $a\ge 0,b\ge 0,n\in {{N}^{*}}$
Giải:
Với $n=1$ , mệnh đề đúng
Giả sử mệnh đề đúng với $n=k\left( k\ge 1 \right)$ : $\Leftrightarrow \frac{{{a}^{k}}+{{b}^{k}}}{2}\ge {{\left( \frac{a+b}{2} \right)}^{k}}\left( 1 \right)$
Ta phải chứng minh: $\frac{{{a}^{k+1}}+{{b}^{k+1}}}{2}\ge {{\left( \frac{a+b}{2} \right)}^{k+1}}$
Thật vậy, ta nhân hai vế của $\left( 1 \right)$ với $\frac{a+b}{2}$ , ta có:
$\Leftrightarrow \frac{{{a}^{k}}+{{b}^{k}}}{2}.\frac{a+b}{2}\ge {{\left( \frac{a+b}{2} \right)}^{k}}.\frac{a+b}{2}={{\left( \frac{a+b}{2} \right)}^{k+1}}$
$\Leftrightarrow \frac{{{a}^{k+1}}+{{a}^{k}}b+a{{b}^{k}}+{{b}^{k+1}}}{4}\ge {{\left( \frac{a+b}{2} \right)}^{k+1}}\left( 2 \right)$
Nhưng với $a>0,b>0$ thì: $\left( {{a}^{k}}-{{b}^{k}} \right)\left( a-b \right)\ge 0\Leftrightarrow {{a}^{k+1}}+{{b}^{k+1}}\ge {{a}^{k}}b+a{{b}^{k}}$
$\Rightarrow \frac{{{a}^{k+1}}+{{a}^{k}}b+a{{b}^{k}}+{{b}^{k+1}}}{4}\le \frac{{{a}^{k+1}}+{{b}^{k+1}}}{2}\left( 3 \right)$
Từ $\left( 2 \right)$ và $\left( 3 \right)$ suy ra điều phải chứng minh.
VD 6: Xác định công thức tổng quát ${{u}_{n}}$ của dãy sau:
.png)
Giải:
Ta có: ${{u}_{2}}=\frac{{{2}^{3}}+1}{{{2}^{3}}},{{u}_{3}}=\frac{{{2}^{4}}+1}{{{2}^{4}}},{{u}_{4}}=\frac{{{2}^{5}}+1}{{{2}^{5}}},...$ Dự đoán: ${{u}_{n}}=\frac{{{2}^{n+1}}+1}{{{2}^{n+1}}}$
Chứng minh bằng phương pháp quy nạp toán học
Với $n=1$ , mệnh đề đúng
Giả sử mệnh đề đúng với $n=k\left( k\ge 1 \right):{{u}_{k}}=\frac{{{2}^{k+1}}+1}{{{2}^{k+1}}}$
Ta cần chứng minh mệnh đề đúng với $n=k+1$ , tức là ${{u}_{k+1}}=\frac{{{2}^{k+2}}+1}{{{2}^{k+2}}}$
Thật vậy, ta có: ${{u}_{k+1}}=\frac{{{u}_{k}}+1}{2}=\left( \frac{{{2}^{k+1}}+1}{{{2}^{k+1}}}+1 \right).\frac{1}{2}=\frac{{{2}^{k+2}}+1}{{{2}^{k+2}}}$
Vậy ${{u}_{n}}=\frac{{{2}^{n+1}}+1}{{{2}^{n+1}}}\left( \forall n\ge 1 \right)$
III/ BÀI TẬP
Bài 1: Chứng minh với $\forall n\in {{N}^{*}}$ thì:
a/ $1+2+...+n=\frac{n(n+1)}{2}$
b/ ${{1}^{2}}+{{2}^{2}}+...+{{n}^{2}}=\frac{n(n+1)(2n+1)}{6}$
c/ ${{1}^{3}}+{{2}^{3}}+{{3}^{3}}+...+{{n}^{3}}=\frac{{{n}^{2}}{{(n+1)}^{2}}}{4}$
d/ $1.4+2.7+...+n(3n+1)=n{{(n+1)}^{2}}$
Bài 2: Chứng minh với $\forall n\in {{N}^{*}}$ ta luôn có:
a/ ${{n}^{3}}+2n$ chia hết cho 3
b/ ${{10}^{n}}+18n-28$ chia hết cho 27
c/ ${{5.2}^{2n-2}}+{{3}^{3n-1}}$ chia hết cho 19
d/ ${{5}^{2n+1}}+{{2}^{n+4}}+{{2}^{n+1}}$ chia hết cho 23
Bài 3: Chứng minh rằng với mọi số nguyên dương n, ta luôn có bất đẳng thức: a/ $1+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{n}}<2\sqrt{n}$
b/ $\frac{1}{n+1}+\frac{1}{n+2}+...+\frac{1}{3n+1}>1$
Bài 4: Chứng minh rằng mọi số tự nhiên $n\ge 3$ ta luôn có:
${{2}^{n}}>2n+1$
Bài 5: Chứng minh rằng với mọi số nguyên n không âm, ta có:
${{3}^{3n+3}}-26n-27$ chia hết cho 169
Bài 6: Chứng minh răng số đường chéo của một đa giác lồi n cạnh là $\frac{n\left( n-3 \right)}{2}$
Bài 7: Cho tổng ${{S}_{n}}=\frac{1}{1.5}+\frac{1}{5.9}+\frac{1}{9.13}+...+\frac{1}{\left( 4n-3 \right)\left( 4n+1 \right)}$ , với $n\in {{N}^{*}}$
Hãy dự đoán công thức tính ${{S}_{n}}$ và chứng minh bằng phương pháp quy nạp
Bài 8: Chứng minh răng số đường chéo của một đa dáng lồi n cạnh $(n\ge 4)$ là $\frac{n\left( n-3 \right)}{2}$
