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