Proof by induction that the function is 9*2^n It works for n=0 Let G(n)=9*99*9999...*(10^2^n-1) Let F(n) be the sum of the digits of that number Now for the inductive step G(N+1)=G(N)(10^2^(N+1)-1) 10^2^(2n+1) has 2^(n+1)+1 digits (and more digits than G(n) which would have less than 2^(n+1)-1 by the sum of a geometric series formula) Now we can see G(N+1)=10^2^(N)*G(N)-G(N) The sum of the digits of 10^2^(N)*G(N)= F(N) Since the last digit of G(a) is 1 or 9, it is greater than 0. When we subtract G(N) from 10^2^(N)*G(N) the last number of G(N) decreases by 1 and the number after it increases by 9, so that really is an increase of 8. Now when you carry over several digits like 1000000-234233, it becomes 999990+10-234233 With the 8 added on we have 9*2^(N+1) when we subtract F(N)=9*2^(N) from that we have 9*2^(N) add that to 9*2^(N)we have have 9*2^(N+1) so for any number N, it works for N+1

$9*99*9999*...*(10^{2^n}-1) = (10-1)(10^2-1)(10^4-1)...(10^{2^n}-1)$ Let $x=10$ $(x-1)(x^2-1)(x^4-1)...(x^{2^n}-1)$ when expanded the exponents that have an even number of zeroes in binary (witih leading zeroes) would have a coeffieicent of $1$ while those wih an odd number of zeroes would have a coefficient of $-1$ because the zeroes represent multiplying by $-1$ instead of a power of $x$ and the $-1$ is multiplied an odd number of times To get $8$ the pos/neg of itself and the two cofficients after must be + - -. For this to happen the number's binary must end with $11$ or $1001$ or $100001$ or ..... The ways to end with $11$ are $2^{n-1}$ and to have an even number of zeroes there are $2^{n-2}$. Similarly, the ways to end with $1001$ is $2^{n-4}$ and this repeats until there it goes to $2$ and then $1$ if $n$ is odd. So use geometric sequence to get $2\frac{(4^{(n-1)/2}-1)}{3}+1=2\frac{(2^{n-1}-1)}{3}+1=\frac{2^n+1}{3}$ If $n$ is even its just a normal geometric sequence so its $2^{n-2}+2^{n-4}+...+1=\frac{4^{n/2}-1}{3}=\frac{2^n-1}{3}$ Because it has to divide $9$, the number of $8$s is the same as the number of $1$s and the total sum is the number above mutliplied by $9$ To get $9$ pos/neg of itself and the next coefficients must be -+. This happens if the binary ends with $1$ or $100$ or $10000$ or .... The ways to end with $11$ is $2^n$ and to have an even number of zeroes, there are $2^{n-1}$ ways. Similar logic applies for other possible endings so the total ways is $2^{n-1}+2^{n-3}+...+1$ If $n$ is odd, use geometric sequence to get $\frac{4^{(n+1)/2}-1}{3}=\frac{2^{n+1}-1}{3}$ If $n$ is even, then its $2^{n-1}+2^{n-3}+...+2+1$, so it becomes $\frac{2^{n+1}+1}{3}$ The total sum is also the above number multiplied by $9$ So the total becomes $\frac{2^{n+1}+2^n}{3} = \frac{2*2^n+2^n}{3}=\frac{3*2^n}{3}=2^n$, but multiply it by $9$ to get $\boxed{9*2^n}$