Number of integers $0 \leq n < 10^6$ that have digits summing to no more than 35 I have seen questions to find the solution where it is $x_1+x_2+...+x_n=k$, but never $x_1+x_2+...+x_n<k$. My thinking to a solution is turn it from $x_1+x_2+x_3+x_4+x_5+x_6<35$ into $x_1+x_2+x_3+x_4+x_5+x_6+r=35$, where $r$ is the remainder after summing $x_1$ to $x_6$, which reduces to $\binom{36+6-1}{36}=\binom{41}{36}=749398$. Is this the correct way to approach this or is there a different method for the general case $x_1+x_2+...+x_n<k$?
 A: You want to count solutions to
$$
x_1+x_2+\dots+x_6\le 35,\\
0\le x_i\le 9,\quad 1\le i\le 6
$$
To replace $\le 35$ with $=35$, introduce a slack variable, as you said:
$$
x_1+x_2+\dots+x_6+x_7= 35,\\
0\le x_i\le 9,\quad 1\le i\le 6\\
0\le x_7\hspace{3.2cm}
$$
The solution is the coefficient of $t^{35}$ in the generating function
$$
(t^0+t^1+\dots+t^9)^6(t^0+t^1+t^2+\dots)=(1-t^{10})^6(1-t)^{-7}
$$
Now, 
$$(1-t^{10})^6=\sum_{k\ge 0}\underbrace{\binom{6}k(-1)^k}_{a_{10k}}t^{10k}.$$ 
and 
$$(1-t)^{-7}=\sum_{k\ge 0}\binom{-7}{k}(-t)^k=\sum_{k\ge 0}\underbrace{\binom{k+6}{6}}_{b_k}t^k,$$ 
We recover the coefficient of $t^{35}$ in the product $(1-t^{10})^6(1-t)^{-7}$ by convolving:
$$
\sum_{k=0}^3\underbrace{(-1)^k\binom{6}{k}}_{a_{10k}}\;\;\underbrace{\binom{(35-10k)+6}{6}}_{b_{35-10k}}
$$
A: At least personally, my setup would be as below.
This setup uses generating functions. This is a technique very handy for this situation, and is the exact situation into which my combinatorics class introduced the notion of generating functions. They're a very powerful counting tool. I'm not sure if you seek a more elementary method, but I'll try to explain in as succinct and detailed a manner as possible.

The integers in $[0,10^6)$ are all $6$ digits at most, or exactly $6$ if we include leading $0$'s. Thus, each number has the form $x_1x_2x_3x_4x_5x_6$ (where the juxtaposition of these is concatenation, not multiplication: for example $x_1=...=x_6=1$ is the number $111,111$). Each $x_i$ is in the set $\{0,1,...,9\}$. Let this number be called $n$.
Within this restriction, we desire the sum of $n$'s digits to be no more than $35$. Ergo, we seek the number of nonnegative integer solutions to 
$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 \leq 35$$
One means of approach would be finding the number of integer solutions for $\sum x_i = 0$, $\sum x_i = 1$, and so on, up to $35$. So for now, let the desired digit sum be $r$; then we seek the number of nonnegative integer solutions to
$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = r$$
This is a type of problem is typically solved through the generating function method. We define polynomials $P_i(x)$ based on the restrictions on each $x_i$. $P_i(x)$ here will be a polynomial whose exponents of the variable $x$ will be the permissible values for $x_i$. Thus, here,
$$P_i(x) = 1+x+x^2+...+x^9 \;\;\;\; \forall i \in \{0,1,...,9\}$$
Thus the generating function for this problem is the product of these polynomials:
$$g(x) = P_1(x)P_2(x)...P_6(x) = (1+x+x^2+...+x^9)^6$$
since $P_1(x)=P_2(x)=...=P_6(x)$. We can simplify this by the formula for a finite geometric sum:
$$1+x+...+x^9 = \frac{x^{10}-1}{x-1} \implies g(x) = \left( \frac{x^{10}-1}{x-1} \right)^6 = (x^{10} - 1)^6 \cdot (x-1)^{-6}$$
The left factor of $g$ can be expanded by using the binomial theorem, and the right factor by using the generalization of that theorem to negative exponents.
$$ (x^{10} - 1)^6 = \sum_{k=0}^6 \binom{6}{k} (-1)^k x^{10k}$$
$$(x-1)^6 = \sum_{j=0}^\infty \binom{6+j-1}{6-1} x^k = \sum_{j=0}^\infty \binom{j+5}{5}  x^j$$
Thus, $g$ becomes
$$g(x) = \sum_{k=0}^6 \binom{6}{k} (-1)^k x^{10k} \cdot \sum_{j=0}^\infty \binom{j+5}{5}  x^j$$
What is the point of all this manipulation in $g$? Recall that we seek the number of solutions to $\sum x_i = r$. Well, as it happens, that answer is the coefficient of $x^r$ in the expansion of $g(x)$ - these manipulations are necessary to find that coefficient in as easy a manner as possible without manually multiplying out $(1+...+x^9)^6$.
So, we have the sum of two polynomials (if we consider the infinite summation on the right a polynomial of infinite degree, for whatever sense that makes). Then it should strike you as obvious that the coefficient of $x^r$ would take one term from the left sum and another from the right sum, whose exponents of $x$ sum to $r$, no?
So recall: we seek the coefficient of $r$ for $r=0,1,...,35$. For $r=0,...,9$, we will require $k=0$ in $g$ and $j=r$. So we plug $k=0,j=r$ into each summation and look at the coefficient of each $x$ term in the sum, and then multiply them.
Once $r\geq 10$, things get messier. For $r=10$, we could have $k=1,j=0$ or $k=0,j=10$. We will sum the coefficients up in each case: take $k=1,j=0$ multiply them, and the same for $k=0,j=10$, summing them together.
Similar results follow with all later $r$. In general, our result becomes
$$\sum_{r=0}^{35} \sum_{\substack{10k+j=r \\ j,k\in \Bbb N \cup \{0\} }}  (-1)^k \binom{6}{k} \binom{j+5}{5}$$

Finding this sum is largely an exercise in algebra and tedium, so I won't elaborate on it. The end goal is that, for each $r$, you would find $j,k$ such that $10k+j=r$, and for each such $j,k$ you would find $(-1)^k \binom{6}{k} \binom{j+5}{5}$ and sum them all up. 
This can be tedious since you have a lot of cases to account for; it might be something doable with a program of some sort. I tried to get WolframAlpha to calculate it but to no avail, and I am too bad at coding to trust my own results.
I don't know if this is necessarily the easiest way to do it. I'm also not fully sure if your solution is valid, OP - generating functions just make far more sense to me for some reason than the comparatively basic method you use. I'm mostly just throwing this out there as a possible alternative.
