_|2^n|n²
0| 1 |0
1| 2 |1
2| 4 |4
3| 8 |9
4| 16 |16
5| 32 |25
6| 64 |36
7|128|49
----------------------------------------------------------------------
2n² >= (n+1)²
2n² >= n² + 2n + 1
n² - 2n - 1 >= 0
= b² - 4ac = 8
r = (2
) / 2a = 1
2
comme on travaille dans
on élimine la valeur négative on garde r = 2,41... donc r = 3
donc 2n² >= (n+1)² pour tout n >= 3
-----------------------------------------------------------------------
récurrence :
init:
n = 4 : 2^4 = 16 4² = 16
donc 2^n >= n² pour n=4
hypothèse de récurrence :
2^n >= n² vrai pour tout n>=4
démontrons le à n+1 :
2^(n+1) >= (n+1)² ???
d'après l'hyp de réc nous avons:
2^n >= n² pour n>=4
2*2^n >= 2*n² pour n>=4
2^(n+1) >= 2n² pour n>=4
nous savons aussi que :
2n² >= (n+1)² pour tout n>3
donc :
2^(n+1) >= 2n² >= (n+1)² pour tout n>=4
donc hyp de réc vrai à l'init, pour n>4, pour n+1, n>=4 donc vrai pour tout n>=4
finalement : 2^n >= n² pour tout n>=4
^^