Prove that the number of vectors in sphere of radius r centered at vector u S-r(u) is $\sum_{i=0}^r \binom{i}{n} (q-1)^i$

Question

I am having a problem understanding this. I would totally appreciate for any help.

Prove that the number of vectors in sphere of radius $r$ centered at vector $u \in \mathbb{F}_q^n$ $S_r(u)$ is $\sum_{i=0}^r \binom{i}{n} (q-1)^i$, where

$S_r(u) = \{v \in \mathbb{F}_q^n \lvert d(u,v) \leq r\} $ and $d(u, v)$ is the hamming distance of the vectors $u$ and $v$ in $\mathbb{F}_q^n$.

My analysis is this,

If I take an element $u \in \mathbb{F}_q^n$, then the remaining vectors left in $\mathbb{F}_q^n$ is $q-1$. Taking the distance starting from the center to $r$ it takes that there are $r$ processes. I don't know know the existence of combinations existence in the formula.

please help me with this.

Answer 1

The correct formula is $\sum_{i=0}^r {n\choose i} (q-1)^i$.

To see this, note that $n\choose i$ is the number of $i$-element subsets of the set $\{1,\ldots,n\}$.

Thus the partial sum ${n\choose i} (q-1)^i$ describes the number of ways to fill $i$ positions of the $n$ coordinate positions with nonzero elements of $GF(q)$.

The outer summation ranges from $0$ (zero vector) to the radius $r$.