Indukcja, udowodnienie podzielności przez 2

[bajtek]

Witam, mam znowu problemy z udowadnianiem podzielności indukcyjnie...

Udowodnij że \(\displaystyle{ n^{2}+n}\) jest podzielne przez 2.

Czy ktoś może mi wytłumaczyć jak najbardziej prosto, bez skrótów, krok po kroku jak to wykonać ? Przejrzałem już mase zadań tutaj na forum i w sieci, i mimo tego wciąż nie łapię jak się to rozwiązuje

[ares41]

Wyłącz \(\displaystyle{ n}\) przed nawias i zasada szufladkowa.-- 17 sie 2011, o 17:33 --Edit// nie doczytałem, że ma być indukcyjnie.

A więc, pokaż nam najpierw pierwszy krok indukcyjny, a potem zaproponuj jak miałby wyglądać drugi.

[bajtek]

\(\displaystyle{ n^{2}+n}\) jest podzielne przez 2.

1) \(\displaystyle{ n^{2}+n}\), dla \(\displaystyle{ n=1}\)
\(\displaystyle{ 1^{2}+1=2}\)

\(\displaystyle{ 2}\) jest podzielne przez \(\displaystyle{ 2}\), zatem wszystko się zgadza.

2) założenie:
zakładam, że podana liczba \(\displaystyle{ n^{2}+n}\) jest podzielna przez \(\displaystyle{ 2}\) dla \(\displaystyle{ n=k}\).

\(\displaystyle{ \frac{( k^{2}+k )}{2} = a}\), gdzie \(\displaystyle{ a \in \mathbb{N}}\)
\(\displaystyle{ ( k^{2}+k ) = 2a}\)

3) teza:
twierdzę, że podana liczba \(\displaystyle{ n^{2}+n}\) jest podzielna przez \(\displaystyle{ 2}\) dla \(\displaystyle{ n=k+1}\).

\(\displaystyle{ \frac{ (k+1)^{2}+(k+1)}{2} = b}\), gdzie \(\displaystyle{ b \in \mathbb{N}}\)
\(\displaystyle{ (k+1)^{2}+(k+1) = 2b}\)


Następnie punkt 4, czyli dowód którego nie wiem jak przeprowadzić...
Wykonanie tych trzech punktów podpatrzyłem w innych zadaniach, ale prawdę powiedziawszy, nie wiem czy zrobiłem je dobrze, ani czy dobrze w nich rozumuję.

[ares41]

Po prostu rozpisz \(\displaystyle{ (k+1)^2+k+1}\), a potem tak pogrupuj to co otrzymasz, aby móc skorzystać z założenia indukcyjnego.

[bakala12]

Zauważ, że \(\displaystyle{ (k+1)^{2}+(k+1)=k^{2}+2k+1+k+1=...}\)
No i skorzystaj z założenia indukcyjnego.-- 17 sie 2011, o 18:14 --ares41, byłeś pierwszy

[bajtek]

No więc tak:

\(\displaystyle{ (k+1)^{2}+(k+1) = k ^{2} + 2k +1 + k + 1 = k ^{2} + k + 2k + 2 = 2a + 2k + 2}\)

\(\displaystyle{ 2k + 2}\) jest podzielne przez \(\displaystyle{ 2}\); z założenia \(\displaystyle{ 2a}\) również jest. Zatem całe wyrażenie \(\displaystyle{ (k+1)^{2}+(k+1)}\) jest podzielne przez \(\displaystyle{ 2}\).


Czy to o to chodzi?

[ares41]

Tak o to. Dobrze jest z wyrażenia po ostatnim znaku równości wyciągnąć dwójkę przed nawias i wtedy od razu widać tą podzielność.

[bajtek]

I to jest naprawdę wszystko :O? ? O kurcze.

Dobrze, w takim razie pytanie: w punkcie 3) oznaczyłem \(\displaystyle{ (k+1) ^{2} + (k+1)}\) jako \(\displaystyle{ 2b}\). Zrobiłem tak, bo podpatrzyłem to u innych, ale czy ma to jakiś sens? Tzn, nie wykorzystałem tego później w żaden sposób...

[ares41]

Jeżeli wyłączyłbyś dwójkę tak jak napisałem wyżej, to wtedy przez \(\displaystyle{ b}\) oznaczasz wyrażenie \(\displaystyle{ a+k+1}\).

[bajtek]

Czyli to pełni jedynie funkcję skrótu?


No dobrze, a taki przykład:

\(\displaystyle{ 2 ^{2n+1} + 3n + 7}\), podzielność przez \(\displaystyle{ 9}\).

1) dla \(\displaystyle{ n = 1}\)

\(\displaystyle{ 2 ^{2+1} + 3 + 7 = \frac{18 }{9} = 2}\).

zgadza się

2) założenie:
dla \(\displaystyle{ n = k}\)

\(\displaystyle{ 2 ^{2k+1} + 3k + 7 = 9a}\), \(\displaystyle{ a \in N}\)

3) teza:
dla \(\displaystyle{ n = k + 1}\)

\(\displaystyle{ 2 ^{2(k+1) +1} + 3(k+1) + 7 = 9b}\), \(\displaystyle{ b \in N}\)

4) dowód:

\(\displaystyle{ 2 ^{2(k+1) +1} + 3(k+1) + 7 = 2 ^{2k + 2 + 1} + 3k + 3 + 7 = 2 ^{2k+1} \cdot 2 ^{2} + 3k + 7 + 3 =}\)
i co dalej? Mam wyrażenie z założenia, ale nie mogę powiedzieć że się wszystko zgadza z powodu tego mnożenia. I jest jeszcze ta \(\displaystyle{ 3}\). Jak to przekształcić, aby wszystko się zgadzało?

[ares41]

Już pierwszy krok jest źle. Nie możesz tego zapisywać w ten sposób.

[bajtek]

\(\displaystyle{ 2 ^{2n+1} + 3n + 7}\), udowodnić podzielność przez 9.

1) \(\displaystyle{ 2 ^{2n+1} + 3n + 7}\), dla \(\displaystyle{ n = 1}\)

\(\displaystyle{ 2 ^{2+1} + 3 + 7 = \frac{18 }{9} = 2}\)
liczba jest podzielna dla \(\displaystyle{ n = 1}\)

2) założenie:

Liczba \(\displaystyle{ 2 ^{2n+1} + 3n + 7}\) jest podzielna przez \(\displaystyle{ 9}\) dla \(\displaystyle{ n = k}\)
\(\displaystyle{ 2 ^{2k+1} + 3k + 7 = 9a, a \in N}\)

3) teza:
Liczba \(\displaystyle{ 2 ^{2n+1} + 3n + 7}\) jest podzielna przez \(\displaystyle{ 9}\) dla \(\displaystyle{ n = k + 1}\)
\(\displaystyle{ 2 ^{2(k+1) +1} + 3(k+1) + 7 = 9b, b \in N}\)

4) dowód:

\(\displaystyle{ 2 ^{2(k+1) +1} + 3(k+1) + 7 = 2 ^{2k + 2 + 1} + 3k + 3 + 7 = 2 ^{2k+1} \cdot 2 ^{2} + 3k + 7 + 3 =}\)



Ok, poprawione, napisałem w stylu poprzedniego zadania.

[ares41]

Dalej pierwszy krok jest źle.
Przecież \(\displaystyle{ 2 ^{2+1} + 3 + 7 \neq 2}\)

[bajtek]

\(\displaystyle{ 2 ^{2+1} + 3 + 7 = \frac{18 }{9} = 2}\)
\(\displaystyle{ 18}\) jest podzielne przez \(\displaystyle{ 9}\), co daje \(\displaystyle{ 2}\) .

Nie mogę tego tak zapisać? Czy mam po prostu stwierdzić, że jest podzielne przez \(\displaystyle{ 9}\) i nie pokazywać wyniku?

edit: aha, łapie o co Ci chodzi, sryy

Ok no to prostu wyrażenie jest podzielne przez \(\displaystyle{ 9}\) dla \(\displaystyle{ n=1}\)

a więc pierwszy krok:

1) \(\displaystyle{ 2 ^{2n+1} + 3n + 7\text{, dla } n = 1}\)

\(\displaystyle{ 2 ^{2+1} + 3 + 7 = 18}\)
liczba jest podzielna przez \(\displaystyle{ 9 \text{ dla }n = 1}\)

[ares41]

Nie mogę tego tak zapisać?

Nie. Piszesz po prostu \(\displaystyle{ 2 ^{2+1} + 3 + 7 =18 =9 \cdot 2}\) skąd od razu widać podzielność przez \(\displaystyle{ 9}\).

-- 18 sie 2011, o 16:44 --

Ok. To jedziemy dalej

\(\displaystyle{ 2 ^{2(k+1) +1} + 3(k+1) + 7 = 2 ^{2k + 2 + 1} + 3k + 3 + 7 =4 \cdot 2 ^{2k+1} + 3k + 10=4(2 ^{2k+1} + 3k + 7) - ....}\)
Dalej dokończ sam i pokaż co Ci wyszło.