The problem is "What is the number of recursive palindromic binary strings of length n ? " A string "s" of length n is recursively palindromic is "s" is a palindrome and the first half of "s", is also recursively palindrome. Example of recursively palindromic strings : 0001000 1011101 111

For example for n = 5, there are four such strings {00000, 00100, 11011, 11111}, so answer is 4.

What I came up with is : T1 = T2 = 2 (n is odd) Tn = 2*T((n-1)/2) (n is even) Tn = T(n/2)

Interestingly . It turns out that Tn = 2^(no. of set bits in binary representation of n) . Can someone explain an intuition behind this simple answer, and how can one come up with this solution ?

Reference : https://discuss.codechef.com/t/official-basic-math-combinatorics-problems/65236/16