• Algorithm
  • Article
  • C
  • Combinatorics
  • Lua
    • Add Me!Close Menu Navigation

    Even Pascals

    Let a=4k-1, where k is an integer. Prove that for any positive integer n the number

        $$ s_n = 1 - {n \choose 2}a + {n \choose 4}a^2 - {n \choose 6}a^3 + \cdots $$

    is divisible by 2^{n-1}.

    Table Of Content

    1. Find a closed form expression of

    2. Find a recurrence relation for

    3. Show that

    1. Find a closed form expression of s_n

    We start with the construction of (a+b)^n.

        \[(a+b)^n = \sum_{k=0}^{n} {n \choose k} a^{n-k}b^k\]

    Since the first term of our series is a one, and the terms alternate in sign on odd powers, we should only consider polynomials (1-x)^n

        \begin{align*} (1-x)^n &= 1 - {n \choose 1}x + {n \choose 2}x^2 - \cdots \end{align*}

    Okay, but we still can’t completely remove the odd terms from the combinations. However, we see that if we were to add in another polynomial of the same degree, we can match up the terms so that the coefficients on the odd {n \choose 2k+1} are canceled. That is, we find the pair x,y such that

        \begin{align*} (1-x)^n + (1+y)^n &= (1+1) + {n \choose 1}(y-x) + {n \choose 2}(y^2 + x^2) + {n \choose 3}(y^3 - x^3) + \cdots \\ \intertext{Therefore, if $y-x=0,y^3-x^3=0,\cdots$, then we can cancel out all the odd terms. Let's set x = y for now} &= 2 +2{n \choose 2}\frac{x^2 + x^2}{2} +2{n \choose 4}\frac{x^4 + x^4}{2} + \cdots \end{align*}

    In order to get s_n, we need to set

        \begin{align*} x^2 &= -a \\ x^4 &= a^2 \\ &\vdots \\ &\implies y = x = \sqrt{-a} \end{align*}

    From this, we get the closed form expression of s_n = \frac{(1 + i\sqrt a)^n + (1 - i\sqrt a)^n}{2}. \blacksquare

    2. Find a recurrence relation for s_n

    This may seem counter-intuitive, but the problem looks like one that can be solved via induction on n, which is much easier to do on a linear recurrence.

    Recall from earlier and differential equation that \frac{(1 + i\sqrt a)^n + (1 - i\sqrt a)^n}{2} is of the form of a linear recurrence with characteristic polynomial whose roots are 1 \pm i\sqrt a. Let’s construct this polynomial in order to find the recurrence.

        \begin{align*} p_s(x) &= (x - (1 + i\sqrt a))(x - (1 - i\sqrt a)) \\ &= ((x-1) + i\sqrt a)((x-1) - i\sqrt a) \\ &= (x-1)^2 + (\sqrt a)^2 \\ &= x^2 - 2x + (a+1) \end{align*}

    Recall that the characteristic polynomial of s_{n+1} = bs_n + as_{n-1} is p_s(x) = x^2 - bx - a, therefore, x^2 - 2x + (a+1) is the characteristic polynomial associated with

        \[s_{n+1} = 2s_n - (a+1)s_{n-1} \hspace{4mm}\mbox{with }s_1=1,s_2=\frac{1-a}{2}\ \blacksquare\]

    3. Show that 2^{n-1}|s_n

    As brought up previously, we will prove this by induction on n. Let P_n \equiv 2^{n-1}|s_n, we will show that P_{n-1},P_n \implies P_{n+1}

        \begin{align*} s_{n+1} &= 2s_n - (a+1)s_{n-1} \\ &= 2(c2^{n-1}) - (4k-1+1)(b2^{n-2}) \\ &= c2^n - bk2^n \\ &= (c-bk)2^n \\ &\implies 2^n|s_{n+1} \\ &\implies P_{n+1} \end{align*}

    This concludes our proof that 2^{n-1}|s_n. \blacksquare

    Posted By Lee

    Woosh