Induktion Analysis 1. Beweise mit vollständiger Induktion: 2n ∈ Ο(2^n)

Question

wie könnte ich hier anfangen ?

Beweise mit vollständiger Induktion: 2n ∈ Ο(2^n) 

Comments

Mit dem Anfang: Krame die Definition von \(\cal O\) raus und schreibe das ohne \(\ldots\in{\cal O}(\ldots)\) hin.

Answer 1

Da genügt doch zu zeigen   2n ≤ 2ⁿ  für alle n aus N⁺.

Für n=1 stimmt es .

wenn es für ein n stimmt, also    2n ≤ 2ⁿ Dann auch                         2* 2n ≤ 2* 2ⁿ 

also                               2* 2n ≤  2ⁿ⁺¹ und weil 2(n+1) = 2n+2 < 2n + 2n = 2* 2n ist, gilt auch

2(n+1) ≤  2ⁿ⁺¹ Und damit ist die Ungl. per vollst. Ind. bewiesen.