Crea sito
RECURSIVE FUNCTIONS


Consider the two functions defined, recursively, on the non-negative integers:

 
Bn(s) = Bn-1(s) ,    0 ≤ s < 2n-1
  = 2Bn-1(s-2n-1) ,    2n-1 ≤ s < 2 n
and  
 
Dn(s) = Dn-1(s/2) ,    s   even
  = 2Dn-1((s-1)/2) ,    s   odd .
Here B0(0) = D0(0) = 1 .
Prove that the two functions are equal.

Marco Corvi - 2003