<s>[INST] Prove $10^{n+1} - 9^{n+1} = 9^n + 9^{n-1}10 + 9^{n-2}10^2 + ... + 10^n$ In this video, James Grime shows that the number of $\mathbb{N}$ less than $10^{n+1}$ that have at least one $3$ among their digits is given by this recurrence relation:
$$T_{n+1} = 9T_{n} + 10^{n}\; where\; T_0=1$$
But later in the video, he says it can also be written as:
$$T_n = 10^{n+1} - 9^{n+1}$$
So, I set out to prove they are the same algebraically:
Solving the recurrence relation, I got:
$$T_n = 9^n + 9^{n-1}10 + 9^{n-2}10^2 + ... + 10^n$$
So, can somebody show me a proof to show that:
$$10^{n+1} - 9^{n+1} = 9^n + 9^{n-1}10 + 9^{n-2}10^2 + ... + 10^n$$
 [/INST] With $a^0=1$, $b^0=1$ for $a, b\ne 0$:
$(a-b)(a^{n}b^{0}+a^{n-1}b^{1}+a^{n-2}b^2+...+a^{1}b^{n-1}+a^{0}b^{n})$
$=a^{n+1}b^{0}+a^{n}b^{1}+a^{n-1}b^2+...+a^{2}b^{n-1}+a^{1}b^{n}-(a^{n}b^{1}+a^{n-1}b^{2}+...+a^{1}b^{n}+a^{0}b^{n+1})$
$=a^{n+1}b^{0}+a^{n}b^{1}+a^{n-1}b^2+...+a^{2}b^{n-1}+a^{1}b^{n}-a^{n}b^{1}-a^{n-1}b^{2}-...-a^{1}b^{n}-a^{0}b^{n+1}$ 
$=a^{n+1}b^{0}+a^{n}b^{1}-a^{n}b^{1}+a^{n-1}b^{2}-a^{n-1}b^{2}+...+a^{1}b^{n}-a^{1}b^{n}-a^{0}b^{n+1}$ 
$=a^{n+1}-b^{n+1}$
This will apply for your problem, because $a-b=10-9=1.$
</s>