3-4. óra, gyakorlat: Teljes indukció
1. feladat: Igazolja,
hogy bármely \(n\in\mathbb N\) esetén:
\[
36\text{ }\big|\text{ }7^n-6n-1
\]
\[
36\text{ }\big|\text{ }7^n-6n-1
\]
Megoldás (fenn van!): (megjelenik)
↓ (eltûnik)
↑
Bizonyítás: teljes
indukcióval.
1. lépés: \(n=0\)-ra: \[ 7^0-6\cdot0-1 = 0\text{; osztható 36-tal.} \] 2. lépés: Legyen \(k\in\mathbb N\) olyan, amelyre az állítás igaz: \[ \color{darkgreen}{36\text{ }\big|\text{ }7^k-6k-1} \] Nézzük \(k+1\)-re: \begin{equation} \begin{split} 7^{k+1}-6(k+1)-1 &= 7\left(\color{darkgreen}{7^k-6k-1}\right) + \overbrace{\color{darkblue}{7\cdot 6k + 7\cdot 1}}^{\text{Ez helyrehozza a csalást...}} \overbrace{- 6(k+1)-1}^{\text{... ez meg volt.}} =\\ &= 7\left(\color{darkgreen}{7^k-6k-1}\right) +42k+7-6k-6-1 =\\ &= \underbrace{7\left(\color{darkgreen}{7^k-6k-1}\right)}_{\text{Ohó 36-tal az ind. felt. miatt...}} +\underbrace{\color{darkgreen}{36}k}_{\text{... ez is.}} \end{split} \end{equation}
1. lépés: \(n=0\)-ra: \[ 7^0-6\cdot0-1 = 0\text{; osztható 36-tal.} \] 2. lépés: Legyen \(k\in\mathbb N\) olyan, amelyre az állítás igaz: \[ \color{darkgreen}{36\text{ }\big|\text{ }7^k-6k-1} \] Nézzük \(k+1\)-re: \begin{equation} \begin{split} 7^{k+1}-6(k+1)-1 &= 7\left(\color{darkgreen}{7^k-6k-1}\right) + \overbrace{\color{darkblue}{7\cdot 6k + 7\cdot 1}}^{\text{Ez helyrehozza a csalást...}} \overbrace{- 6(k+1)-1}^{\text{... ez meg volt.}} =\\ &= 7\left(\color{darkgreen}{7^k-6k-1}\right) +42k+7-6k-6-1 =\\ &= \underbrace{7\left(\color{darkgreen}{7^k-6k-1}\right)}_{\text{Ohó 36-tal az ind. felt. miatt...}} +\underbrace{\color{darkgreen}{36}k}_{\text{... ez is.}} \end{split} \end{equation}
2. feladat: Mutassa
meg, hogy minden \(n\in\mathbb N\) esetén:
\[
12\text{ }\big|\text{ }11^n-3\cdot 7^n+2\cdot 5^n
\]
\[
12\text{ }\big|\text{ }11^n-3\cdot 7^n+2\cdot 5^n
\]
Megoldás (fenn van!): (megjelenik)
↓ (eltûnik)
↑
Bizonyítás: teljes
indukcióval.
1. lépés: \(n=0\)-ra: \[ 11^0-3\cdot7^0+2\cdot5^0 = 1-3+2 = 0\text{; osztható 12-vel.} \] 2. lépés: Legyen \(k\in\mathbb N\) olyan, amelyre az állítás igaz: \[ \color{darkgreen}{12\text{ }\big|\text{ }11^k-3\cdot 7^k+2\cdot 5^k} \] Mi a helyzet \(k+1\)-re? \begin{equation} \begin{split} 11^{k+1}-3\cdot 7^{k+1}+2\cdot 5^{k+1} &= 11\left(\color{darkgreen}{11^k-3\cdot 7^k+2\cdot 5^k}\right) \overbrace{+\color{darkblue}{11\cdot3\cdot7^k}-\color{darkblue}{11\cdot2\cdot5^k}}^{\text{Ez helyrehozza a csalást...}} -3\cdot 7^{k+1}+2\cdot 5^{k+1}=\\ &= 11\left(\color{darkgreen}{11^k-3\cdot 7^k+2\cdot 5^k}\right)+33\cdot7^k-22\cdot5^k -21\cdot7^k+10\cdot5^k=\\ &= \underbrace{11\left(\color{darkgreen}{11^k-3\cdot 7^k+2\cdot 5^k}\right)}_{\text{Ohó 12-vel az ind. felt. miatt...}} + \underbrace{\color{darkgreen}{12}\cdot7^k-\color{darkgreen}{12}\cdot5^k}_{\text{... és ez is ohó 12-vel.}} \end{split} \end{equation}
1. lépés: \(n=0\)-ra: \[ 11^0-3\cdot7^0+2\cdot5^0 = 1-3+2 = 0\text{; osztható 12-vel.} \] 2. lépés: Legyen \(k\in\mathbb N\) olyan, amelyre az állítás igaz: \[ \color{darkgreen}{12\text{ }\big|\text{ }11^k-3\cdot 7^k+2\cdot 5^k} \] Mi a helyzet \(k+1\)-re? \begin{equation} \begin{split} 11^{k+1}-3\cdot 7^{k+1}+2\cdot 5^{k+1} &= 11\left(\color{darkgreen}{11^k-3\cdot 7^k+2\cdot 5^k}\right) \overbrace{+\color{darkblue}{11\cdot3\cdot7^k}-\color{darkblue}{11\cdot2\cdot5^k}}^{\text{Ez helyrehozza a csalást...}} -3\cdot 7^{k+1}+2\cdot 5^{k+1}=\\ &= 11\left(\color{darkgreen}{11^k-3\cdot 7^k+2\cdot 5^k}\right)+33\cdot7^k-22\cdot5^k -21\cdot7^k+10\cdot5^k=\\ &= \underbrace{11\left(\color{darkgreen}{11^k-3\cdot 7^k+2\cdot 5^k}\right)}_{\text{Ohó 12-vel az ind. felt. miatt...}} + \underbrace{\color{darkgreen}{12}\cdot7^k-\color{darkgreen}{12}\cdot5^k}_{\text{... és ez is ohó 12-vel.}} \end{split} \end{equation}
3. feladat: Az
\(a_n\) sorozat definíciója a következõ:
\begin{equation}
\begin{split}
a_0 &= 5\\\\
\text{A rekurzió:}\\
a_{n+1} &= a_n+2n+1
\end{split}
\end{equation}
Igazolja, hogy az \(a_n\) sorozatra fennáll az alábbi képlet:
\[
a_n = n^2+5\text{; }\hphantom{000}n\in\mathbb N
\]
\begin{equation}
\begin{split}
a_0 &= 5\\\\
\text{A rekurzió:}\\
a_{n+1} &= a_n+2n+1
\end{split}
\end{equation}
Igazolja, hogy az \(a_n\) sorozatra fennáll az alábbi képlet:
\[
a_n = n^2+5\text{; }\hphantom{000}n\in\mathbb N
\]
Megoldás (fenn van!): (megjelenik)
↓ (eltûnik)
↑
Bizonyítás: teljes
indukcióval.
1. lépés: \(n=0\)-ra: \[ a_0 = 0^2+5 = 5\text{. Ez rendben van.} \] 2. lépés: Legyen \(k\in\mathbb N\) olyan, amelyre az állítás igaz: \[ \color{darkgreen}{a_k=k^2+5} \] Nézzük \(k+1\)-re: \begin{equation} \begin{split} a_{k+1} &= \color{darkgreen}{a_k} + 2k+1 = \color{darkgreen}{k^2+5} + 2k + 1 = \color{brown}{k^2+2k+1}+5 = \color{brown}{(k+1)^2}+5 \end{split} \end{equation} Tehát a képlet \(k+1\)-re is fennáll.
1. lépés: \(n=0\)-ra: \[ a_0 = 0^2+5 = 5\text{. Ez rendben van.} \] 2. lépés: Legyen \(k\in\mathbb N\) olyan, amelyre az állítás igaz: \[ \color{darkgreen}{a_k=k^2+5} \] Nézzük \(k+1\)-re: \begin{equation} \begin{split} a_{k+1} &= \color{darkgreen}{a_k} + 2k+1 = \color{darkgreen}{k^2+5} + 2k + 1 = \color{brown}{k^2+2k+1}+5 = \color{brown}{(k+1)^2}+5 \end{split} \end{equation} Tehát a képlet \(k+1\)-re is fennáll.
