Numarul de permutari cu timp de sortare egal prin cele doua procedee si care incep cu 1 este fib[2N-3], numarul celor care incep cu 2 este tot fib[2N-3], numarul celor care incep cu 3 este fib[2N-5], cu 4 fib[2N-7]. Avem ca:
fib[1] + fib[3] + fib[5] + … + fib[2N-5] + fib[2N-3] + fib[2N-3] =
fib[2] + fib[3] + fib[5] + … + fib[2N-5] + fib[2N-3] + fib[2N-3] =
fib[4] + fib[5] + … + fib[2N-5] + fib[2N-3] + fib[2N-3] =
…………………………………………………………. =
fib[2N-2] + fib[2N-3] = fib[2N-1].
Demonstratia se face prin inductie. Cand la o permutare cu N elemente adaugam 1 in fata nu se schimba nimic => numarul permutarilor cu N+1 elemente care incep cu 1 este fib[2N-1]. Cand la o permutare cu N elemente adaugam 2 in fata (crescand cu 1 elementele >= 2), evident numarul inversiunilor creste cu 1 si la fel si numarul ciclurilor => adaugam fib[2N-1] la solutie.
Cand adaugam x (x >= 3), permutarea trebuie sa inceapa astfel: x 1 2 … (x-2) P, unde P este o permutare de lungime N-x+2 care trebuie sa aiba propr. ceruta. Numarul permutarilor P este din ipoteza inductiva fib[2*(N-x+2)-1] = fib[2N-2x+3]. Pentru x = 3, 4, 5.. sumam valori de forma fib[2N-3], fib[2N-5], etc si ajungem in final la o suma de forma:
fib[1] + fib[3] + … + fib[2N-5] + fib[2N-3] + fib[2N-1] + fib[2N-1] = fib[2N+1], ceea ce trebuia demonstrat.