udowodnić indukcyjnie
-
olcia446
- Użytkownik
- Posty: 46
- Rejestracja: 2 cze 2011, o 22:26
- Płeć: Kobieta
- Lokalizacja: Lublin
- Podziękował: 9 razy
udowodnić indukcyjnie
Udowodnić indukcyjnie, że każdą co najmniej ośmiozłotową opłatę skarbową można uiścić mając do dyspozycji tylko znaczki skarbowe o nominałach \(\displaystyle{ 3}\)zł i \(\displaystyle{ 5}\)zł.
-
mateuszek89
- Użytkownik
- Posty: 1106
- Rejestracja: 1 lip 2010, o 15:27
- Płeć: Mężczyzna
- Lokalizacja: toruń
- Pomógł: 153 razy
udowodnić indukcyjnie
1. Sprawdzamy dla \(\displaystyle{ n=8}\) czy istnieją takie \(\displaystyle{ x,y \in \mathbb{N}_{0}}\), że \(\displaystyle{ 3x+5y=8}\). Oczywiście \(\displaystyle{ 3 \cdot 1 + 5 \cdot 1=8}\) więc ok.
2. Założenie. Istnieją takie \(\displaystyle{ x,y \in \mathbb{N}_{0}}\), że \(\displaystyle{ 3x+5y=n}\) dla jakiegoś \(\displaystyle{ n \ge 8}\). Oczywiście \(\displaystyle{ n \in \mathbb{N}}\).
3. Teza. Istnieją \(\displaystyle{ k,l \in \mathbb{N}_{0}}\) takie, że \(\displaystyle{ 3k+5l=n+1}\)
4. Dowód.
a) Jeśli \(\displaystyle{ 3|n}\) to \(\displaystyle{ n=3 \cdot b}\) gdzie \(\displaystyle{ b \ge 3}\) (bo \(\displaystyle{ n \ge 9}\)). Szukamy takich \(\displaystyle{ k,l}\), że:
\(\displaystyle{ 3k+5l=n+1}\)
Zauważmy, że:
\(\displaystyle{ n+1=3x+5y+1=3(x-3)+5(y+2)}\).
Stąd biorąc \(\displaystyle{ k:=x-3}\) oraz \(\displaystyle{ l:=y+2}\) otrzymujemy żądany rozkład. \(\displaystyle{ k,l \in \mathbb{N}_{0}}\), bo \(\displaystyle{ y \in \mathbb{N}_{0}}\) oraz \(\displaystyle{ x \ge 3}\) i \(\displaystyle{ x \in \mathbb{N}_{0}}\).
b) \(\displaystyle{ n}\) nie jest podzielne przez \(\displaystyle{ 3}\). Wtedy z równania \(\displaystyle{ 3x+5y=n}\) możemy wywnioskować, że \(\displaystyle{ y \ge 1}\). Szukamy takich \(\displaystyle{ k,l \in \mathbb{N}_{0}}\), że:
\(\displaystyle{ 3k+5l=n+1}\)
Zauważmy, że:
\(\displaystyle{ n+1=3x+5y+1=3(x+2)+5(y-1)}\).
Stąd biorąc \(\displaystyle{ k:=x+2}\) i \(\displaystyle{ l:=y-1}\) otrzymujemy żądany rozkład. Oczywiście \(\displaystyle{ k,l \in \mathbb{N}_{0}}\).
Pozdrawiam!
2. Założenie. Istnieją takie \(\displaystyle{ x,y \in \mathbb{N}_{0}}\), że \(\displaystyle{ 3x+5y=n}\) dla jakiegoś \(\displaystyle{ n \ge 8}\). Oczywiście \(\displaystyle{ n \in \mathbb{N}}\).
3. Teza. Istnieją \(\displaystyle{ k,l \in \mathbb{N}_{0}}\) takie, że \(\displaystyle{ 3k+5l=n+1}\)
4. Dowód.
a) Jeśli \(\displaystyle{ 3|n}\) to \(\displaystyle{ n=3 \cdot b}\) gdzie \(\displaystyle{ b \ge 3}\) (bo \(\displaystyle{ n \ge 9}\)). Szukamy takich \(\displaystyle{ k,l}\), że:
\(\displaystyle{ 3k+5l=n+1}\)
Zauważmy, że:
\(\displaystyle{ n+1=3x+5y+1=3(x-3)+5(y+2)}\).
Stąd biorąc \(\displaystyle{ k:=x-3}\) oraz \(\displaystyle{ l:=y+2}\) otrzymujemy żądany rozkład. \(\displaystyle{ k,l \in \mathbb{N}_{0}}\), bo \(\displaystyle{ y \in \mathbb{N}_{0}}\) oraz \(\displaystyle{ x \ge 3}\) i \(\displaystyle{ x \in \mathbb{N}_{0}}\).
b) \(\displaystyle{ n}\) nie jest podzielne przez \(\displaystyle{ 3}\). Wtedy z równania \(\displaystyle{ 3x+5y=n}\) możemy wywnioskować, że \(\displaystyle{ y \ge 1}\). Szukamy takich \(\displaystyle{ k,l \in \mathbb{N}_{0}}\), że:
\(\displaystyle{ 3k+5l=n+1}\)
Zauważmy, że:
\(\displaystyle{ n+1=3x+5y+1=3(x+2)+5(y-1)}\).
Stąd biorąc \(\displaystyle{ k:=x+2}\) i \(\displaystyle{ l:=y-1}\) otrzymujemy żądany rozkład. Oczywiście \(\displaystyle{ k,l \in \mathbb{N}_{0}}\).
Pozdrawiam!
-
MichalKulis
- Użytkownik
- Posty: 47
- Rejestracja: 19 sty 2011, o 08:15
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
udowodnić indukcyjnie
Jest mały błąd w podpunkcie a) dowodu. Niekoniecznie \(\displaystyle{ x \ge 3}\).
Weźmy np. \(\displaystyle{ 11 = 3 \cdot 2 + 5 \cdot 1}\) czyli \(\displaystyle{ x=2, y=1}\).
I z tego wnioskujemy, że można przedstawić 12 w następującej formie: \(\displaystyle{ 12 = 3 \cdot k + 5 \cdot l}\) gdzie \(\displaystyle{ k=x-3=-1, l=y+2=3}\). Czyli dostajemy \(\displaystyle{ k<0}\). Błąd.
Weźmy np. \(\displaystyle{ 11 = 3 \cdot 2 + 5 \cdot 1}\) czyli \(\displaystyle{ x=2, y=1}\).
I z tego wnioskujemy, że można przedstawić 12 w następującej formie: \(\displaystyle{ 12 = 3 \cdot k + 5 \cdot l}\) gdzie \(\displaystyle{ k=x-3=-1, l=y+2=3}\). Czyli dostajemy \(\displaystyle{ k<0}\). Błąd.