intuition

When N=0, no number is there, or 0 is there. a[0]=1

When N=1, there are k such numbers, or 1..k-1. a[1]=k-1

When N=2, there are k^2-k such numbers.

a[2]=>k^2-k

=>(k-1)k

=>(k-1)(k-1+1)

=>(k-1)(k-1)+(k-1)*1

=>(k-1)a[1] + (k-1)*a[0]

which can be used for all subsequent digits