Calculate how many natural numbers $n$ where $ 0\leq n \leq 10,000,000$ such that the sum of their digits is AT MOST $34$
And I said the following:
We have 8 digits in numbers between $0$ and $10,000,000$. For the first digit there can be only $0$ or $1$. For all rest digits we have all possibilties $[0,...,9]$. So let us do a generating function: $F(x) = (1+x)(1+x+x^2+...+x^9)^7$. We are searching for the coefficients of $1$ and $x$ and $...$ and $x^{34}$. But that is like searching for the coefficient of $x^{34}$ in the generating function $G(x) = (1+x+x^2+...)(1+x)(1+x+x^2+...+x^9)^7$
But how do I continue from there? How can I know the coefficient of $x^{34}$ in $G(x)$?
In comments you have correctly reduced the question to determining the coefficient of $x^{34}$ in $(1-x^{10})^7(1-x)^{-8}$. We can reduce modulo $x^{35}$, in which case the first factor becomes $1-\binom71x^{10}+\binom72x^{20}-\binom73x^{30}=1-7x^{10}+21x^{20}-35x^{30}$. Then it suffices to determine in the factor $(1-x)^{-8}$ the terms of degree $34-10k$ for $k=0,1,2,3$, which can be seen to be repectively $\binom{-8}{34}(-x)^{34}=\binom{41}7x^{34}=22481940x^{34}$, $\binom{-8}{24}(-x)^{24}=\binom{31}7x^{24}=2629575x^{24}$, $\binom{21}7x^{14}=116280x^{14}$, and $\binom{11}7x^4=330x^4$. Utlimately I find the coefficient $$ 22{,}481{,}940x-7\times2{,}629{,}575+21*116{,}280-35*330=6{,}505{,}245. $$ Just a sanity check: that's more than half of all numbers $n<10^7$; indeed the average sum of $7$ digits is $7\times4.5=31.5$, so it is more likely the sum is at most $34$ than the contrary. The final outcome of course is $6{,}505{,}245+1=6{,}505{,}246$.