On Monday, I posed two puzzles from PyCon. The commenters there have pretty much covered everything, but I wanted to post my own approach.

For the sum of the digits in the number of palindromes between zero and a googol, first think about how many palindromes there are with 2n digits. Each is formed by joining an n-digit number with its reverse, so there are as many 2n-digit palindromes as there are n-digit numbers. The number of n-digit numbers is all combinations of n digits, 10ⁿ, except you can’t have a leading zero, so remove all those, for a total of 10ⁿ - 10^n-1.

The number of palindromes with 2n-1 digits is the same, since you just remove one of the doubled center digits.

The number of palindromes between zero and 10¹⁰⁰ is then:

for n = 1 to 50, sum 2 × (10ⁿ - 10^n-1)

Refactoring and expanding the summation:

2 × (10⁵⁰ - 10⁴⁹ + 10⁴⁹ - 10⁴⁸ + ... + 10¹ - 10⁰)

Most of the terms in the summation cancel each other out, leaving:

2 × (10⁵⁰ - 1)

This is 199999999999999999999999999999999999999999999999998, the number of palindromes between 0 and 10¹⁰⁰. It has 49 9’s, for a digit sum of 1+49×9+8, or 450.

For the stairs problem, let’s call the number of ways to walk up a flight of n stairs, S(n). We know that S(1) is 1, and S(2) is 2. For the arbitrary case n, there are two possible ways to start up the stairs, you can take the first step, or you can skip the first step. If you take the first, there are S(n-1) ways to finish your walk. If you skip the first, there are S(n-2) ways to finish it. So S(n) = S(n-1) + S(n-2). Combined with our values for S(1) and S(2), we see that S is the classic Fibonacci series: 1, 2, 3, 5, 8, 13, 21, 34, etc.