Binomial theorem and modular arithmetic

In summary: Thus, by the definition of congruence, ## b_n = 0 (3) ## iff ## a_n = 0 (3) ##, which is equivalent to the original statement.In summary, the given expression is the solution to a linear recurrence relation with specific initial conditions and can be reduced to a periodic sequence with period 4. This leads to the conclusion that the original statement is true.
  • #1
Quesadilla
95
13

Homework Statement


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##.

Homework Equations


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

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.
 
Physics news on Phys.org
  • #2
Quesadilla said:

Homework Statement


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##.

Homework Equations


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

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.

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.
 
  • Like
Likes 1 person
  • #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 ##.
 

1. What is the binomial theorem?

The binomial theorem is a mathematical formula that allows us to expand a binomial expression raised to a positive integer power. It is written as (a + b)^n = a^n + nC1 * a^(n-1)b + nC2 * a^(n-2)b^2 + ... + nCn * b^n, where nCk represents the binomial coefficient or the number of ways to choose k objects from a set of n objects.

2. How is the binomial theorem related to modular arithmetic?

The binomial theorem has a direct connection to modular arithmetic through the binomial coefficient. In modular arithmetic, we are concerned with remainders after dividing by a certain number. The binomial coefficient helps us calculate these remainders efficiently, especially when dealing with large numbers.

3. What is modular arithmetic?

Modular arithmetic is a type of arithmetic where numbers "wrap around" after reaching a certain value, called the modulus. It is used to solve problems related to remainders and cyclic patterns. In modular arithmetic, we are working with a finite set of numbers and operations are performed on remainders rather than actual numbers.

4. How is modular arithmetic used in cryptography?

Modular arithmetic is an essential tool in cryptography, particularly in creating secure encryption algorithms. The use of modular arithmetic ensures that encrypted messages are nearly impossible to decrypt without the correct key. It also helps in generating random numbers, which are crucial in creating secure keys.

5. Can the binomial theorem be extended to non-integer powers?

Yes, the binomial theorem can be extended to non-integer powers using the binomial series. This series is an infinite sum of terms involving the binomial coefficient, and it converges to the desired value when the power is not a positive integer. This extension is crucial in many areas of mathematics, such as calculus and complex analysis.

Similar threads

  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
14
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
421
Replies
12
Views
827
  • Calculus and Beyond Homework Help
Replies
1
Views
253
  • Calculus and Beyond Homework Help
Replies
18
Views
1K
  • Calculus and Beyond Homework Help
Replies
17
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
356
  • Calculus and Beyond Homework Help
Replies
3
Views
444
  • Calculus and Beyond Homework Help
Replies
2
Views
658
Back
Top