x^2 kleiner gleich 2^x Behauptung beweisen

Question

Wie sieht eine vollständige Induktion für diese Aussage aus?

∀ x ∈ ℕ , x  > 4,   x^{2 <}   2^x

^{Muss der Anfang nicht so aussehen:}

(x + 1) ² < 2 ^{x +1}

^{Wie komme ich weiter?}

Answer 1

Induktionsanfang: n = 4

n = 4

4^2 ≤ 2^4

16 ≤ 16

Induktionsschritt: n --> n + 1

(n + 1)^2 ≤ 2^{n + 1}

n^2 + 2·n + 1 ≤ 2·2^n

n^2 + 2·n + 1 ≤ 2·n^2

2·n + 1 ≤ n^2

n^2 - 2·n - 1 ≥ 0

n ≥ √2 + 1 = 2.414

Das ist aber bei n ≥ 4 sicher gegeben.

Answer 2

Erst mal prüfen, ob es für x = 4 stimmt.

Dann angenommen für ein x gilt      x^{2 <}   2^x        #  damit

herleiten, dass auch (x + 1) ² < 2 ^{x +1}    gilt.

Etwa so    x^{2 <}   2^x       | *2

==>       2x² <   2*2^x      

==>       x² + x² <   2^x+1     

Da für alle x≥4 aber x² ≥2x+1 gilt,

(Das könnte durch  x² ≥2x+1  <=>  x² - 2x+1 ≥ 2 <=>  ( x-1)² ≥ 2

                    bewiesen werden .)

hast du 

          x²  +2x+1  <     x² + x² <  2^x+1    

                  (x+1)² <  2^x+1     q.e.d.