Indukcja matematyczna - podstawy Kopdaw: Indukcja matematyczna − podstawy. Witam, czy mógłby mi ktoś wyjaśnić w jaki sposób zostało udowodnione poniższe zadanie? n² < 2ⁿ dla n ≥ 5 Przeprowadźmy dowód indukcyjny. Pokażmy najpierw, że 2n+1 < 2ⁿ (dla zupełnie dowolnego n ≥ 3) Oczywiście 2 * 3 + 1 = 7 < 8 =2³ Oraz 2(n+1)+ 1 = 2n+3 <2ⁿ+4 = 2ⁿ+2² ≤ 2ⁿ + 2ⁿ = 2 * 2ⁿ = 2ⁿ⁺¹ A następnie: zauważamy, że 5²=25<32=2⁵ oraz, że (n+1)² = n² + (2n+ 1) < 2ⁿ +2ⁿ = 2 * 2ⁿ = 2ⁿ⁺¹. Nie rozumiem już właściwie początku: 2n+1 < 2ⁿ (dla zupełnie dowolnego n ≥ 3) skąd 2n (skoro wcześniej mam n²) i skąd n ≥ 3 zamiast 5?

Godzio: Nie dziwię się, że nie rozumiesz, skoro to jest dowód typu "udowodnijmy coś, żeby później tego nie udowadniać" − i właściwie nie wiadomo skąd to się bierze, dowód lepiej przeprowadzić tak: Sprawdzamy dla n = 5 Działa ! Zakładamy prawdziwość dla dowolnego n ≥ 5, zatem mamy: n² < 2ⁿ, pokażemy dla n + 1 : (n + 1)² =n² + 2n + 1, ale z założenia mamy, że n² < 2ⁿ, wiec szacujemy to przez: 2ⁿ + 2n + 1 < 2ⁿ + 2ⁿ = 2^{n + 1}, skorzystaliśmy tu z faktu, że 2ⁿ > 2n + 1, dla n ≥ 3 (czyli tym bardziej dla 5, która nas najbardziej interesuje), później dowód dla 2ⁿ > 2n + 1 i koniec zadania, a jak widać najpierw zaczęliśmy od tego nie wiedząc czemu

Kopdaw: Dzięki − dużo jaśniej ale jeszcze nie do końca − to moje pierwsze starcie z tym tematem. Skąd bierze się 2n + 1 − skoro tam wychodzi 2ⁿ⁺¹ oraz dlaczego dla n ≥ 3? Ta trójka nie mam pojęcia skąd się wzięła.

Kopdaw: ref

Godzio: 2n + 1 bierze się z podniesienia (n + 1) do kwadratu: (n + 1)² = n² + 2n + 1 < 2ⁿ + 2n + 1, a my chcemy na końcu otrzymać ... > 2^{n + 1}, a żeby to osiągnąć to 2n + 1 musi być mniejsze od 2ⁿ Skąd się bierze 3 ? Ano stąd, że to najmniejsza liczba naturalna, dla które nierówność 2n + 1 < 2ⁿ działa ! Sprawdźmy. n = 1 3 > 2 n = 2 5 > 4 n = 3 7 < 8 Działa, pozostaje pokazać, że dla kolejnych n również działa, a to robimy indukcyjnie

Kopdaw: Chyba jestem zbyt ciemny... rozumiem do momentu, gdzie mam 2ⁿ +2n + 1... dalej nie wiem dlaczego ma być ">" od 2ⁿ⁺¹ oraz nie wiem skąd bierze się to 2ⁿ + 2ⁿ. Nie można po prostu zamiast n podstawić wszędzie n+1? W sensie: (n+1)² < 2ⁿ⁺¹ n² + 2n + 1 < 2^k+1 ? Jak dalej to dowodzić?

Artur_z_miasta_Neptuna: nie 2^k+1 tylko 2ⁿ⁺¹ (n+1)² = n²+2n+1 < //na mocy założenia// 2ⁿ +(2n+1) ale czy 2ⁿ + 2n + 1 < 2ⁿ⁺¹ tego nie wiesz ... ale chcesz to właśnie wykazać zauważ, że 2ⁿ⁺¹ = 2ⁿ*2 = 2ⁿ + 2ⁿ <−−− działania na potęgach czyli brakuje Ci takiego kroku: 2ⁿ + 2n+1 < 2ⁿ + 2ⁿ = 2ⁿ⁺¹ czyli: 2n+1 < 2ⁿ a to jest prawdą dla n≥3 (jak chcesz może to wykazać ... np. indukcyjnie )

Kopdaw: Zgoda − 2ⁿ⁺¹ = 2ⁿ * 2¹ Natomiast 2ⁿ⁺¹ to 2ⁿ + 2ⁿ Tylko z drugiej strony nie rozumiem: 2ⁿ + 2n+1 −−> 2ⁿ + ..... .... − z tej strony nie rozumiem

Artur_z_miasta_Neptuna: skoro 2ⁿ⁺¹ = 2ⁿ*2 to 2ⁿ*2 = 2ⁿ*(1+1) = 2ⁿ*1 + 2ⁿ*1 = 2ⁿ + 2ⁿ ... prawda a to właśnie jest 'kluczowy moment' dowodu pokazanie że 2n+1 < 2ⁿ dla n≥3

Kopdaw: Prawda − pisząc 2ⁿ*(1+1) to widać od razu, że to będzie 2ⁿ + 2ⁿ Ja nie widzę po prostu tego przekształcenia: 2ⁿ + 2n+1 −−> 2ⁿ*(1+1) dokładniej "+ 2n+1" na "*(1+1)" co się dzieje z tym "n"?