SOLUTIONS

No problem is ever permanently closed. Any comments, new solutions, or new insights on old problems are always welcomed by the editor.

3. Proposed by Curtis Cooper and Robert E. Kennedy, Central Missouri State University, Warrensburg, Missouri.

The Fibonacci numbers F_{n} satisfy F_{0} = 0, F_{1} = 1, and
F_{n+2} = F_{n+1} + F_{n} for n = 0, 1, 2, ….

Show that

∑_{i=1}^{n} F_{i}^{3} = \frac{1}{10}F_{3n+2} + \frac{3}{5}(−1)^{n−1}F_{n−1} + \frac{1}{2} .

Solution by Joe Flowers, Northeast Missouri State University, Kirksville, Missouri and Dale Woods, Central (Oklahoma) State University, Edmond, Oklahoma (jointly).

The proof is by induction on n and use of the well-known

explicit formula F_{n} = \frac{1}{\sqrt{5}}(a^{n} −b^{n}) where a = \frac{1+\sqrt{5}}{2} and b = \frac{1−\sqrt{5}}{2} .

Note that a · b = −1.

For n = 1,

\frac{1}{10}F_{5} + \frac{3}{5}F_{0} + \frac{1}{2} = \frac{5}{10} + 0 + \frac{1}{2} = 1,

as required. Now assume that

∑_{i=1}^{k} F_{i}^{3} = \frac{1}{10}F_{3k+2} + \frac{3}{5}(−1)^{k−1}F_{k−1} + \frac{1}{2} for some k ≥ 1 .

Then

F_{k+1}^{3} = \frac{1}{5\sqrt{5}}(a^{k+1} − b^{k+1})^{3}

= \frac{1}{5\sqrt{5}}(a^{3k+3} − 3a^{2k+2}b^{k+1} + 3a^{k+1}b^{2k+2} − b^{3k+3})

= \frac{1}{5\sqrt{5}}(a^{3k+3} − b^{3k+3}) − \frac{1}{5\sqrt{5}}(3a^{k+1}b^{k+1})(a^{k+1} − b^{k+1})

= \frac{1}{5}F_{3k+3} − \frac{3}{5}(−1)^{k+1}F_{k+1},

and therefore

∑_{i=1}^{k+1} F_{i}^{3} = ∑_{i=1}^{k} F_{i}^{3} + F_{k+1}^{3}

= \frac{1}{10}F_{3k+2} + \frac{3}{5}(−1)^{k−1}F_{k−1} + \frac{1}{2} + \frac{1}{5}F_{3k+3} − \frac{3}{5}(−1)^{k+1}F_{k+1}

= \frac{1}{10}F_{3k+2} + \frac{1}{10}F_{3k+3} + \frac{1}{10}F_{3k+3} + \frac{3}{5}(−1)^{k}(F_{k+1} − F_{k−1}) + \frac{1}{2}

= \frac{1}{10}F_{3k+4} + \frac{1}{10}F_{3k+3} + \frac{3}{5}(−1)^{k}F_{k} + \frac{1}{2}

= \frac{1}{10}F_{3k+5} + \frac{3}{5}(−1)^{k}F_{k} + \frac{1}{2} .

Also solved by Russell Euler, Northwest Missouri State University, Maryville, Missouri and the proposers.

4. Proposed by Curtis Cooper, Central Missouri State University, Warrensburg, Missouri.

Let n be a positive integer and P be a permutation on {1, …, n}. Which permutations result in non-contradictory lists of n statements where statement i in the list is

i. Statement P (i) is false. Solution by Charles J. Allard, Polo R-VII High School, Polo,

Missouri.

The permutations leading to non-contradictory lists of n statements are the ones which are the products of disjoint cycles of even length.

To see this, let (i_{1}, i_{2}, …, i_{m}) be one of the cycles in the factorization of P. Then

i_{1}. Statement i_{2} is false.
i_{2}. Statement i_{3} is false.
⋮
i_{m}. Statement i_{1} is false.

Now all the statements cannot be false (since that would imply all the statements are true). Without loss of generality, suppose statement i_{1} is true. Then statement i_{2} is false so statement i_{3} is true. Continuing in the above manner; if m is even, statement i_{m} is false; whereas if m is odd, statement i_{m} is true. Thus if m is even, statement i_{1} is true; but if m is odd, statement i_{1} is false, a contradiction.

Therefore, the only non-contradictory permutations are the ones which are the product of disjoint cycles of even length. It might be noted that if n is odd, none of the permutations are noncontradictory.

Also solved by the proposer.

5. Proposed by Curtis Cooper and Robert E. Kennedy, Central Missouri State University, Warrensburg, Missouri.

Show

∑_{j=0}^{10}(2 cos \frac{2πj}{11} )^{11} = 22 .

Solution I. by Larry Eifler, University of Missouri - Kansas City, Kansas City, Missouri.

Let n be a positive integer and set ω = e^{\frac{2πi}{n}} . Then
S_{n} = ∑_{j=0}^{n−1}(2 cos \frac{2π}{n} j)^{n}

= ∑_{j=0}^{n−1}(ω^{j} + ω^{−j})^{n}

= ∑_{j=0}^{n−1}[∑_{k=0}^{n} \binom{n}{k}ω^{jk}ω^{−j(n−k)}]

= ∑_{j=0}^{n−1}[∑_{k=0}^{n} \binom{n}{k}ω^{2jk}]

= ∑_{k=0}^{n}[\binom{n}{k} ∑_{j=0}^{n−1} ω^{2kj}] .

Since

(ω^{2k} − 1) ∑_{j=0}^{n−1} ω^{2kj} = ω^{2kn} − 1 = 0 ,

we have

∑_{j=0}^{n−1} ω^{2kj} = \{ \begin{matrix}n, & if ω^{2k} = 1; \\ 0, & if ω^{2k} ≠ 1 . \end{matrix}

Thus,

S_{n} = \{ \begin{matrix}2n, & if n is odd; \\ 2n + n\binom{n}{\frac{n}{2}}, & if n is even . \end{matrix}

Solution II. by James Horner, Central Missouri State University, Warrensburg, Missouri.

Let

S(m, q) = ∑_{j=0}^{m−1}(2 cos \frac{qπj}{m} )^{m}

where q is an even integer and q and m are relatively prime. Also,

let x = exp(\frac{qπi}{m}) and note that x^{p} = 1 if and only if p is an integer

multiple of m.

Now,

S(m, q) = ∑_{j=0}^{m−1}(x^{j} + x^{−j})^{m} = ∑_{j=0}^{m−1} x^{−mj}(x^{2j} + 1)^{m}

= ∑_{j=0}^{m−1}(x^{2j} + 1)^{m} = ∑_{j=0}^{m−1} ∑_{k=0}^{m} \binom{m}{k}x^{2jk}

= ∑_{k=0}^{m} \binom{m}{k} ∑_{j=0}^{m−1} x^{2kj} .

For 0 ≤ k ≤ m, x^{2k} = 1 only when k = 0 and k = m. Then,

∑_{j=0}^{m−1} x^{2kj} = \{ \begin{matrix}m, & if k = 0 or k = m; \\ \frac{1−x^{2km}}{1−x^{2k}} = 0, & if k ≠ 0 and k ≠ m . \end{matrix}

Thus,

S(m, q) = [\binom{m}{0} + \binom{m}{m}] · m = 2m .

Solution III. by James Horner, Central Missouri State University, Warrensburg, Missouri.

Let q and m be positive integers with qm even. With x = exp(\frac{qπi}{m}),

S(m, q) = ∑_{j=0}^{m−1}(2 cos \frac{qπj}{m} )^{m} = ∑_{j=0}^{m−1}(x^{j} + x^{−j})^{m}

= ∑_{j=0}^{m−1} x^{−mj}(x^{2j} + 1)^{m} = ∑_{j=0}^{m−1} x^{−mj} ∑_{k=0}^{m} \binom{m}{k}x^{2jk}

= ∑_{k=0}^{m} \binom{m}{k} ∑_{j=0}^{m−1} x^{(2k−m)j} .

We note that x^{p} = 1 if and only if \frac{qp}{m} is an even integer, and consider two cases.

When q is even, x^{2k−m} = 1 if and only if \frac{qk}{m} is an integer. Also, 0 ≤ k ≤ m. So, x^{2k−m} = 1 only when k = 0 or k is of the form \frac{m}{p}, where p is a common divisor of m and q.

Let 1 = p_{1} < p_{2} < p_{3} < ⋯ < p_{n} be the common divisors of m and q and let k_{0} = 0 and k_{i} = \frac{m}{p_{i}} for 1 ≤ i ≤ n. Then,

∑_{j=0}^{m−1} x^{(2k−m)j} = \{ \begin{matrix}m, & if k ∈ \{k_{i} : 0 ≤ i ≤ n\}; \\ \frac{1−x^{(2k−m)m}}{1−x^{2k−m}} = 0, & otherwise . \end{matrix}

Thus, when q is even,

S(m, q) = m ∑_{i=0}^{n} \binom{m}{k_{i}} .

We note that if m and q are relatively prime (as, for example, q = 2 and m = 11), S(m, q) = 2m).

Suppose now that q is odd and m is even. In this case, x^{2k−m} =

1 if and only if (\frac{2k}{m} − 1) is an even integer. So, we must have \frac{2k}{m}

an odd integer and we have 0 ≤ k ≤ m. The only choice is k = \frac{m}{2}.

Thus, in this case, S(m, q) = m\binom{m}{\frac{m}{2}} .

Also solved by James Horner, Central Missouri State University, Warrensburg, Missouri (three solutions); Joseph Chance, Pan American University, Edinburg, Texas; Alejandro Necochea, Pan American University, Edinburg, Texas; Edward Wang, Wilfrid Laurier University, Waterloo, Ontario, Canada, and the proposers.

Wang notes that there is a well-known identity

∏_{j=1}^{n} sin \frac{πj}{n} = \frac{n}{2^{n−1}}

for all integers n. Thus from this and the problem we obtain the

interesting identity

(∗)  ∑_{j=0}^{n−1}(cos \frac{2πj}{n} )^{n} = ∏_{j=1}^{n} sin \frac{πj}{n} .

for all odd integers n. Wang asks if there is a direct proof of (*).