If $n = 2^k - 1$ for $k \in \mathbb{N}$, then every entry in row $n$ of pascal's triangle is odd. Prove: If $n = 2^k - 1$ for $k \in \mathbb{N}$, then every entry in row $n$ of pascal's triangle is odd.
I know that the $n$th row in pascal's triangle correspond to the coefficients of $(x+y)^n$:
$$\begin{align}(x+y)^n = {n \choose 0} x^n + {n \choose 1} x^{n-1} y + {n \choose 2}x^{n-2}y^2+{n \choose 3} x^{n-3} + \cdots + {n \choose n-1} xy^{n-1}+{n \choose n} y^n \end{align}.$$ 
I have to show that each coefficient $\begin{align} {n \choose 0},{n \choose 1},{n \choose 2},\ldots,{n \choose n-1},{n \choose n} \end{align}$ is of the form $2b+1$, but I'm not sure how to do this with $n =2^k-1$.
 A: Hint: $\binom{2^n-1}{k-1}+\binom{2^n-1}{k} = \binom{2^n}{k}$. Show that $\binom{2^n}{k}$ is always even for $k\neq 0,2^n$.
A: An easy way to prove that $\binom{2^n-1}{k}$ is odd for every $k\leq2^n-1$ is the following: 
We can write
$$\binom{2^n-1}{k}=\frac{(2^n-1)(2^n-2)......(2^n-k)}{k!}$$Now note this: For every $i\in\{1.....k\}$ the factorization of $2^n-i$ contains the same powers of 2 that contains $i$ infact suppose $i=2^tc$ where c is odd then $2^n-i=2^n-2^tc=2^t(2^{n-t}-c)$.
i.e  if $$2^t||i\Rightarrow 2^t||(2^n-i)$$
Then simplifying the fraction from powers of 2 we obtain an odd number for every k.
A: As the answer above says, $\displaystyle{2^{n}-1\choose k-1}+{2^{n}-1\choose k} = {2^n \choose k}$. So if  ${2^n \choose k}$ is even for $k \neq 0,2^n$, both terms are even or both terms are odd. First, let's prove that ${2^n \choose k}$ is even.
$$\displaystyle{2^n \choose k} = \frac{2^n!}{k!(2^n-k)!}$$
For $k = 1, {2^n \choose 1} = 2^n$ even. Now assume ${2^n \choose k}$ is even for some k, now: 
$$\displaystyle{2^n \choose k} = \frac{2^n!}{k!(2^n-k)!} = \frac{2^n!(k+1)}{(k+1)!(2^n-k-1)!(2^n-k)} = {2^n \choose k+1}\frac{k+1}{2^n-k}$$
Now, if $k$ is either odd or even, $\displaystyle\frac{k+1}{2^n-k}$ is odd. As $\displaystyle{2^n \choose k}$ is even, it has to happen that $\displaystyle{2^n \choose k+1}$ must be even. Therefore by induction, $\displaystyle{2^n \choose k}$ is even for all $k \neq 0,2^n$.
Now, by induction as $\displaystyle{2^{n}-1\choose k-1}+{2^{n}-1\choose k} = {2^n \choose k}$, note that, as the first two terms ($k = 0,1$) are odd, then the third term must also be odd, and so on.
Therefore ${2^n-1 \choose k}$ is odd for all $k$ between $0$ and $2^n-1$.
A: Based on @Thomas Andrews: answer: 
For $p$ prime and $0< k < p^n$,  $\displaystyle\binom{p^n}{k}$ is divisible by $p$. Using 
$$\binom{p^n-1}{k-1}+ \binom{p^n-1}{k}=\binom{p^n}{k}$$
we conclude
$$\binom{p^n-1}{k} \equiv (-1)^k \ ( \!\!\!\!\!\! \mod p)$$
For example: $\displaystyle\binom{24}{8} = 735471 \equiv (-1)^8 \ ( \!\!\!\!\! \mod 5)$
A: Counting the Number of Factors of $\boldsymbol{2}$
In Corollary $(7)$ of this answer, it is shown that the number of factors of $p$ in $\binom{n}{k}$ is
$$
\frac{\sigma_p(k)+\sigma_p(n-k)-\sigma_p(n)}{p-1}\tag{1}
$$
where $\sigma_p(n)$ us the sum of the digits in the base-$p$ representation of $n$.
In base-$2$, each digit of $n=2^k-1$ is a $1$. For $0\le k\le n$, each digit of $k$ that is a $0$ is a $1$ in $n-k$ and vice-versa. Thus, $\sigma_p(k)+\sigma_p(n-k)=\sigma_p(n)$. Thus, formula $(1)$ says that there are $0$ factors of $2$ in $\binom{n}{k}$.
That is, $\binom{n}{k}$ is odd.

Induction
We will show that for $n\ge1$,
$$
\binom{2^n}{k}\text{ is even for }0\lt k\lt2^n\tag{2}
$$
and of course $\binom{2^n}{0}=\binom{2^n}{2^n}=1$.
Note that $(2)$ is true for $n=1$. Suppose that $(2)$ is true for some $n$. Then we can use Vandermonde's Identity to get
$$
\binom{2^{n+1}}{k}=\sum_{j=0}^k\binom{2^n}{j}\binom{2^n}{k-j}\tag{3}
$$
where inductively, $\binom{2^n}{j}\binom{2^n}{k-j}$ is even except when either $j=0$ or $j=2^n$ and either $k-j=0$ or $k-j=2^n$. That gives $4$ cases:


*

*$j=k=0$: makes $\binom{2^{n+1}}{0}$ odd

*$j=0$ and $k=2^n$: paired with case 3, makes $\binom{2^{n+1}}{2^n}$ even

*$j=2^n$ and $k=2^n$: paired with case 2, makes $\binom{2^{n+1}}{2^n}$ even

*$j=2^n$ and $k=2^{n+1}$: makes $\binom{2^{n+1}}{2^{n+1}}$ odd
Thus, accounting for these $4$ special cases, $(3)$ shows that $(2)$ holds for $n+1$.

Since $\binom{2^n-1}{0}=1$ and for $0\lt k\lt2^n$
$$
\binom{2^n-1}{k}=\binom{2^n}{k}-\binom{2^n-1}{k-1}\tag{4}
$$
we get that $\binom{2^n-1}{k}$ is odd (even minus odd) for $0\le k\le2^n-1$.
