1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Binomial theorem and modular arithmetic

  1. Aug 28, 2014 #1
    1. The problem statement, all variables and given/known data
    From an old exam: Show that
    \begin{equation*}
    \sum_{0 \leq 2k \leq n} \binom{n}{2k}2^k = 0 (3) \text{ iff } n = 2 (4).
    \end{equation*}
    By ##a = b (k)## I mean that ##a## is congruent to ##b## modulo ##k##.

    2. Relevant equations
    Binomial theorem: ## (a + b)^m = \sum_{k=1}^m \binom{k}{m} a^k b^{m-k}##.

    3. The attempt at a solution
    A hint was provided to consider ##\frac{1}{2}((1 + \sqrt{2})^n + (1 - \sqrt{2})^n) ##.

    I have taken some baby steps. Using the binomial theorem, I was able to establish
    \begin{equation*}
    \sum_{0 \leq 2k \leq n} \binom{n}{2k}2^k = \frac{1}{2}((1 + \sqrt{2})^n + (1 - \sqrt{2})^n).
    \end{equation*}
    Now in other words I need to find for exactly which ##n## the above is divisible by ##3##, which I guess is equivalent to saying that ## ((1 + \sqrt{2})^n + (1 - \sqrt{2})^n) ## is divisible by ##6##.

    I would greatly appreciate some small hints.
     
  2. jcsd
  3. Aug 28, 2014 #2

    pasmith

    User Avatar
    Homework Helper

    Given that [itex]a_n = A\lambda_1^n + B\lambda_2^n[/itex] is the general solution of the linear recurrence relation [tex]a_{n+2} - (\lambda_1 + \lambda_2)a_{n+1} + \lambda_1\lambda_2a_n = 0,[/tex] I am motivated to view [itex]\frac12((1 + \sqrt{2})^n + (1 - \sqrt{2})^n)[/itex] as being the solution of that recurrence relation with [itex]\lambda_{1} = 1 + \sqrt{2}[/itex], [itex]\lambda_2 = 1 - \sqrt{2}[/itex] and initial conditions [itex]a_0 = a_1 = 1[/itex], and consider [itex]b_n = a_n \mod 3[/itex]. I suspect you will find that [itex]b_n[/itex] is periodic with period equal to some multiple of 4.
     
  4. Aug 28, 2014 #3
    Thank you, Pasmith.

    It seems highly plausible that I was expected to identify the expression as the solution to that linear recurrence relation, which I assume is what you did by inspection.

    Indeed, by considering ## b_n = a_n (3) ## I use the recurrence relation to find that ##b_n## is periodic and ##b_n = 0 (3) ## exactly when ## n = 2 + 4m ##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Binomial theorem and modular arithmetic
  1. Modular arithmetic (Replies: 3)

  2. Modular arithmetic (Replies: 6)

  3. Modular Arithmetic (Replies: 23)

  4. Modular arithmetic (Replies: 3)

Loading...