Induktion

[varberg0]

Hej!

Jag vill gärna ha hjälp med detta problem.


Låt M(n) beteckna antalet bit-operationer som behövs för att multiplicera två n-bitars heltal. Man kan visa att

M(2n)<=3M(n)+Cn,

där C är en positiv konstant.
Visa med hjälp av denna olikhet och induktion att för k>=1 gäller

M(2^k)<=B(3^k - 2^k),

där B=max(M(2),C)

Tack på förhand.
varberg0
[/sub]