t(1) = 1
t(n) = 2*t(n-1) + 1
t(n-1) = 2*t(n-2) + 1
t(n) = 2*(2t(n-2) + 1) + 1 = 2*2*t(n-2) + 2 + 1
t(n-2) = 2*t(n-3) + 1
t(n) = 2*2*(2*t(n-3) + 1) + 2 + 1
= 2*2*2*t(n-3) + 4 + 2 + 1
= 2**(n-1) + 2**(n-2) + 2**(n-3) =?= 2**n - 1 :
mais oui !!! en binaire 111 = 1000 - 1
=> Comment démontrer qu'en binaire : 111 = 1000 - 1 ?
c'est à dire que Somme(2**i) pour i=(n-1) à 0 = 2**n - 1