证明组合和式∑_{k=0}^{n} \binom{2n+1}{2k}3^k可被2ⁿ整除

Let's break this problem into two clear parts: first verifying the equality between the two sums, then proving the sum is divisible by (2^n).

Part 1: Proving the Equality #

We can use the binomial theorem with radical terms to simplify both sides and show they're identical.

Step 1: Simplify the Left-Hand Side (LHS) #

The LHS is:
[
\sum_{k=0}^{n} \binom{2n+1}{2k} 3^k
]
Notice (3^k = (\sqrt{3})^{2k}), so this sum captures the even-indexed terms of the binomial expansion of ((1+\sqrt{3})^{2n+1}). Using the standard identity for separating even/odd binomial terms:
[
\sum_{k=0}^{m} \binom{2m+1}{2k} x^{2k} = \frac{(1+x)^{2m+1} + (1-x)^{2m+1}}{2}
]
Substitute (x = \sqrt{3}) and (m = n):
[
\text{LHS} = \frac{(1+\sqrt{3})^{2n+1} + (1-\sqrt{3})^{2n+1}}{2}
]

Step 2: Simplify the Right-Hand Side (RHS) #

The RHS is:
[
\sum_{k=0}^{2n} \binom{2n}{k} 3^{\lceil k/2 \rceil}
]
Split the sum into even and odd values of (k):

• For even (k = 2m): (\lceil k/2 \rceil = m), so the term is (\binom{2n}{2m}3^m)
• For odd (k = 2m+1): (\lceil k/2 \rceil = m+1), so the term is (\binom{2n}{2m+1}3^{m+1})

This splits the RHS into two separate sums:
[
\text{RHS} = \sum_{m=0}^{n} \binom{2n}{2m}3^m + 3\sum_{m=0}^{n-1} \binom{2n}{2m+1}3^m
]
Apply binomial term separation identities again:

• (\sum_{m=0}^{n} \binom{2n}{2m}3^m = \frac{(1+\sqrt{3})^{2n} + (1-\sqrt{3})^{2n}}{2})
• (\sum_{m=0}^{n-1} \binom{2n}{2m+1}3^m = \frac{(1+\sqrt{3})^{2n} - (1-\sqrt{3})^{2n}}{2\sqrt{3}})

Substitute these into the RHS:
[
\text{RHS} = \frac{(1+\sqrt{3})^{2n} + (1-\sqrt{3})^{2n}}{2} + 3 \cdot \frac{(1+\sqrt{3})^{2n} - (1-\sqrt{3})^{2n}}{2\sqrt{3}}
]
Simplify the second term ((3/\sqrt{3} = \sqrt{3})) and factor terms:
[
\text{RHS} = \frac{(1+\sqrt{3})^{2n}(1+\sqrt{3}) + (1-\sqrt{3})^{2n}(1-\sqrt{3})}{2} = \frac{(1+\sqrt{3})^{2n+1} + (1-\sqrt{3})^{2n+1}}{2}
]
This matches the simplified LHS, so the equality holds.

Part 2: Proving Divisibility by (2^n) #

We'll use mathematical induction on (n), leveraging the simplified form of the sum we just derived:
[
S(n) = \frac{(1+\sqrt{3})^{2n+1} + (1-\sqrt{3})^{2n+1}}{2}
]

Base Cases #

• For (n=0): (S(0) = \frac{(1+\sqrt{3}) + (1-\sqrt{3})}{2} = 1), which is divisible by (2^0 = 1)
• For (n=1): (S(1) = \frac{(1+\sqrt{3})^3 + (1-\sqrt{3})^3}{2} = \frac{(10+6\sqrt{3}) + (10-6\sqrt{3})}{2} = 10), which is divisible by (2^1 = 2)

Inductive Step #

Assume (S(m)) is divisible by (2^m) for some integer (m \geq 0), meaning (S(m) = 2^m \cdot k) where (k) is an integer.

Now consider (S(m+1)):
[
S(m+1) = \frac{(1+\sqrt{3})^{2m+3} + (1-\sqrt{3})^{2m+3}}{2}
]
Note that ((1+\sqrt{3})^2 = 2(2+\sqrt{3})) and ((1-\sqrt{3})^2 = 2(2-\sqrt{3})). Substitute these into the expression:
[
(1+\sqrt{3})^{2m+3} = (1+\sqrt{3})^{2m+1} \cdot 2(2+\sqrt{3})
]
[
(1-\sqrt{3})^{2m+3} = (1-\sqrt{3})^{2m+1} \cdot 2(2-\sqrt{3})
]
Cancel the factor of 2 in the numerator and denominator:
[
S(m+1) = (2+\sqrt{3})(1+\sqrt{3})^{2m+1} + (2-\sqrt{3})(1-\sqrt{3})^{2m+1}
]
Expand and rearrange terms:
[
= 2\left[(1+\sqrt{3})^{2m+1} + (1-\sqrt{3})^{2m+1}\right] + \sqrt{3}\left[(1+\sqrt{3})^{2m+1} - (1-\sqrt{3})^{2m+1}\right]
]
We know:

• ((1+\sqrt{3})^{2m+1} + (1-\sqrt{3})^{2m+1} = 2S(m))
• Let (T(m) = \frac{(1+\sqrt{3})^{2m+1} - (1-\sqrt{3})^{2m+1}}{2\sqrt{3}}) (an integer, since radicals cancel out), so (\sqrt{3}[...] = 6T(m))

Substitute back:
[
S(m+1) = 4S(m) + 6T(m)
]
Using the inductive hypothesis (S(m) = 2^m k):
[
S(m+1) = 4 \cdot 2^m k + 6T(m) = 2^{m+1}(2k + 3T(m))
]
Since (2k + 3T(m)) is an integer, (S(m+1)) is divisible by (2^{m+1}). The inductive step holds.

Thus, by induction, (S(n)) is divisible by (2^n) for all non-negative integers (n).

内容的提问来源于stack exchange，提问作者StefanH