Prove that the ∑ i = 0 n 2 3 i ( 2 n + 1 2 i + 1 ) is never divisible by 5.

Question

Prove that the       ∑          i      =      0        n        2          3      i                          (                            2        n        +        1                    2        i        +        1                            )             is never divisible by   5.

baselulaox · Accepted Answer

Since it has already been established in the comments that a linear recurrence will do the job, here's a brief outline of that method that I hope doesn't give away too much.
Working

m o d 5

, we set

a_{n} = \sum_{i = 0}^{n} 3^{i} (\binom{2 n + 1}{2 i + 1}),

, so that

a_{0} = 1

and

a_{1} = 6,

and show that

a_{n}

satisfies the linear recurrence

a_{n} = 8 a_{n - 1} - 4 a_{n - 2}, n \geq 2,

from which it follows that

a_{n},

, and thus the sum in the question, is never congruent to zero

m o d 5

.
To add some more detail note that

a_{n} = \sum_{i = 0}^{n} 3^{i} (\binom{2 n + 1}{2 i + 1}) = \frac{(\sqrt{3} + 1)^{2 n + 1} + (\sqrt{3} - 1)^{2 n + 1}}{2 \sqrt{3}} .

Teagan Huffman · Accepted Answer

Set   S  (  n  )  =      ∑          i      =      0        n        2          3      i                                    (                                      2          n          +          1                          2          i          +          1                                      )                    , using Zeilberger&#039;s algorithm, we can find the recurrence  S  (  n  +  2  )  =  18  S  (  n  +  1  )  −  49  S  (  n  )  ,    n  ≥  0  ,with initial value   S  (  0  )  =  1 and   S  (  1  )  =  11. Mod 5 both sides, we have  S  (  n  +  2  )      ≡    5    3  S  (  n  +  1  )  +  S  (  n  )  ,    n  ≥  0  ,with initial value   S  (  0  )      ≡    5    S  (  1  )      ≡    5    1. It is easy to see that  S  (  12  k  )      ≡    5    S  (  12  k  +  1  )      ≡    5    S  (  12  k  +  8  )      ≡    5    1  ,  S  (  12  k  +  5  )      ≡    5    S  (  12  k  +  9  )      ≡    5    S  (  12  k  +  10  )      ≡    5    2  ,  S  (  12  k  +  3  )      ≡    5    S  (  12  k  +  4  )      ≡    5    S  (  12  k  +  11  )      ≡    5    3  ,  S  (  12  k  +  2  )      ≡    5    S  (  12  k  +  6  )      ≡    5    S  (  12  k  +  7  )      ≡    5    4.

Prove that the Sum^n_(i=0) 2^(3i)((2n+1)/(2i+1)) is never divisible by 5

Answered question

Answer & Explanation

New Questions in Precalculus