1
$\begingroup$

Like the title says, I'm to prove that if $n=2^k-1$ then all entries of the nth row of Pascal's Triangle are odd. I know a couple of things that I can use for this, for one I know that I can describe the $j$th entry as $\binom{n}{j}$, and I know that $\binom{n+1}{j} = \binom{n}{j-1} + \binom{n}{j}$. I think the way to go is to show that $\binom{n}{j-1}$ and $\binom{n}{j}$ have opposite parities, thereby showing that their sum must be odd. The clincher is that I'm only allowed to use direct or contrapositive proof, i.e. no induction allowed.

$\endgroup$
2
  • 1
    $\begingroup$ "No induction allowed" ought to be banned from classrooms. It's an elegant form of proof, and if we get into the nitty gritty details, just the fact that we are using the natural numbers means that we are automatically using induction, at least somewhere deep down. $\endgroup$
    – Arthur
    Jan 31 '18 at 15:26
  • 1
    $\begingroup$ Can you prove that $\binom{2^k}j$ is even for $0<j<2^k$? It then follows that $\binom n{j-1}$ and $\binom nj$ have the same parity for all $j$ (since they add up to an even number). But $\binom n0$ is odd. $\endgroup$ Jan 31 '18 at 15:36
4
$\begingroup$

I'd do it this way: the explicit formula for an entry is

$$\binom nj = \dfrac{n!}{j!(n-j)!} = \dfrac{n(n-1)\cdots(n-(j-1))}{j!} = \dfrac{(2^k-1)(2^k-2)\cdots(2^k-j)}{1\cdot 2\cdots j}$$

$2$ divides $2^k-i$ the same number of times it divides $i$ for $1 \leq i \leq j$, so all factors of $2$ on the top and bottom will cancel.

$\endgroup$
7
  • $\begingroup$ Could you be a bit more explicit in the last line of that? $\endgroup$
    – Peatherfed
    Feb 5 '18 at 6:24
  • $\begingroup$ @Peatherfed If we split each $2^k-i$ into prime factors, and each $i$ into prime factors, all the factors of $2$ will cancel. This leaves only odd factors in the numerator, so the number must be odd. Please let me know if this helps. $\endgroup$
    – BallBoy
    Feb 5 '18 at 11:31
  • $\begingroup$ OK, I see it now, it was especially helpful for me two split up that final fraction in the form (2^k-i)/i for 1<i<j. Is there a "rigorous" way to put this, or is what you wrote in your answer acceptable? $\endgroup$
    – Peatherfed
    Feb 15 '18 at 16:36
  • $\begingroup$ @Peatherfed "Acceptable" to whom? $\endgroup$
    – BallBoy
    Feb 15 '18 at 17:49
  • $\begingroup$ In the sense that the answer is rigorous I guess? $\endgroup$
    – Peatherfed
    Feb 16 '18 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.