In the land of Binary, the unit of currency is called Ben and currency notes are available in denominations 1, 2, 22, 23, …. Bens. The rules of the Government of Binary stipulate that one can not use more than two notes of any one denomination in any transaction. For example, one can give $a$ change for 2 Bens in two ways: 2 one Ben notes or 1 two Ben note. For 5 Ben one can give 1 one Ben note and 1 four Ben note or 1 one Ben note and 2 two Ben notes. Using 5 one Ben notes or 3 one Ben notes and 1 two Ben notes for $a$ 5 Ben transaction is prohibited. Find the number of ways in which one can give change for 100 Bens, following the rules of the Government.

Step 1: 1, 2, 22 ……….

Step 2: => $a$ + 2b + 4c + …. = 100 0 \le $a$ \le 2, 0 \le $b$ \le 2 …..

Step 3: a=0 or a=1 a=2

Step 4:  2(b + 2c + …) = 99 

Step 5: b + 2c + …. = 50 =>a=1 $b$ + 2c + ….. = 49

Step 6: not possible => $c$ + 2d + …… = 24

Step 7: Let number of solutions be a100

Step 8: a100 = a50 + a24

Step 9: a100 = (a25 + a24) + a24 = a25 + 2a24

Step 10: = a12 + 2(a12 + a5)

Step 11: = 3a12 + 2a5

Step 12: = 3(a6 + a2) + 2(a2)

Step 13: = 5a2 + 3a6

Step 14: = 5a2 + 3(a3 + a2)

Step 15: = 8a2 + 3a3

Step 16: Let, $a$ + 2b + 4c = 3

Step 17: a = 1 => 2b + 4c = 2

Step 18: => $b$ + 2c = 1

Step 19: => $b$ = 1, $c$ = 0

Step 20: (1, 1, 0) only one solution => a3 = 1

Step 21: (0, 1) (2, 0) => a2 = 2

Step 22: => a100 = 8(2) + 3(1)