Recurrence Relation : How many 1's between 0 to (2^n-1)

Explain:
0
1

Total Number of 1 bit between 0 to 1
O1 = 1


Total Number of 1 bit between 0 to 3 (2^2 - 1)
O2 = 2 + 2*f(1) = 2^(2-1)+ 2*O1

Total Number of 1 bit between 0 to 7 (2^3-1)
O3 =  2^(3-1)+ 2*O2

so the recurrence relation is
On = 2^(n-1) + 2*On-1





Iteration:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

#include<stdio.h> typedef unsigned long long int64; int main(){ int64 O[65],two; int i; O[1]=1; two = 1; printf("Total Number of 1's bits between 0 and %llu:%llu\n",(two<<1)-1,O[1]); for (i=2;i<64;i++){ two = two<<1; O[i] = two + 2*O[i-1]; printf("Total Number of 1's bits between 0 and %llu:%llu\n",(two<<1) -1,O[i]); } return 0; }

Output:

 


Recursion:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include<stdio.h> typedef unsigned long long int64; int64 O[65]; int64 count1(int l){ int64 two =1,a=0; if (l==1) return 1; two = two<<(l-1); return a = a+ (2*count1(l-1))+two; } int main(){ int64 two=1; int i; for (i=1;i<64;i++){ O[i] = count1(i); two = two<<1; printf("Total Number of 1's bits between 0 and %llu:%llu\n",two-1,O[i]); } return 0; }