# Help with a nasty sum of binomial coefficients

I need help with the following sum: $$\sum_{n=1}^k \binom{k}{n}-k \left \lfloor{\frac{\binom{k}{n}}{k} } \right \rfloor$$

I've found that the sum is equivalent to the following: $$\sum_{n=1}^k \binom{k}{n} \mod k$$ But I can't find a closed form for the life of me. Even in terms of special functions, is there a closed form for this sum?

• Does it help that $_kC_n \mod k$ is $0$ when $k$ is prime? – Frpzzd May 13 '17 at 13:41
• Substitute $x=1$ in the Binomial Theorem expansion of $(1+x)^{k}$. – ancientmathematician May 13 '17 at 14:39
• @MichałMiśkiewicz What exactly do you want me to clarify? – TreFox May 13 '17 at 19:47
• As @ancientmathematician commented, why not use Binomial theorem? It is $2^k -1$ mod $k$. – Sungjin Kim May 13 '17 at 20:20