MHB Show the result of the sum of a series isn't a prime number

[anemone]

Show that for an odd integer $m\ge 5$,

$\displaystyle {m\choose 0} 5^{m-1}-{m\choose 1} 5^{m-2}+{m\choose 2} 5^{m-3}-\cdots+{m\choose m-1} $

is not a prime number.

 

[Prove It]

Show that for an odd integer $m\ge 5$,

Spoiler

$\displaystyle {m\choose 0} 5^{m-1}-{m\choose 1} 5^{m-2}+{m\choose 2} 5^{m-3}-\cdots+{m\choose m-1} $

is not a prime number.

Spoiler

$\displaystyle \begin{align*} S &= \sum_{r = 0}^{m-1}{ {m\choose{r}} 5^{m - r - 1} } \\ 5S &= 5\sum_{r = 0}^{m-1}{ {m\choose{r}} 5^{m-r-1} } \\ 5S &= \sum_{r = 0}^{m-1}{ {m\choose{r}} 5^{m-r} } \\ 5S &= \sum_{r = 0}^{m - 1}{ \left[ {m\choose{r}}5^{m-r} \cdot 1^r \right] } \\ 5S + 1 &= \sum_{r = 0}^{m - 1}{ \left[ {m\choose{r}} 5^{m-r} \cdot 1^r \right] } + 1 \\ 5S + 1 &= \sum_{r = 0}^{m - 1}{ \left[ {m\choose{r}} 5^{m - r} \cdot 1^r \right] } + {m\choose{m}} 5^0 \cdot 1^m \\ 5S + 1 &= \sum_{r = 0}^m{ {m\choose{r}} 5^{m - r} \cdot 1^r } \\ 5S + 1 &= \left( 5 + 1 \right) ^m \\ 5S + 1 &= 6^m \\ 5S &= 6^m - 1 \\ S &= \frac{6^m - 1}{5} \end{align*}$

So now we have to prove that $\displaystyle \begin{align*} \frac{6^m - 1}{5} \end{align*}$ is not prime if m is some odd integer greater than or equal to 5. I'm leaning towards induction...

Base step: m = 5

$\displaystyle \begin{align*} \frac{6^5 - 1}{5} &= \frac{7776 - 1}{5} \\ &= \frac{7775}{5} \\ &= 1555 \\ &= 5 \cdot 311 \end{align*}$

This is clearly not prime, so the base step is proven.

Now for the inductive step, assume that the statement is true for m = 2k + 1 (where k is another integer $\displaystyle \begin{align*} \geq 2 \end{align*}$, use this to prove the statement is true for m = 2k + 3.

So we assume $\displaystyle \begin{align*} \frac{6^{2k + 1} - 1}{5} \end{align*}$ is not prime, then

$\displaystyle \begin{align*} \frac{6^{2k + 3} - 1}{5} &= \frac{6^2 \cdot 6^{2k + 1} - 1}{5} \\ &= \frac{36 \cdot 6^{2k + 1} - 36 + 35}{5} \\ &= \frac{36 \left( 6^{2k + 1} - 1 \right) + 35}{5} \\ &= 36 \left( \frac{6^{2k + 1} - 1 }{5} \right) + 7 \end{align*}$

I'm not sure how to prove that this is not prime now...

 

[Saitama]

Show that for an odd integer $m\ge 5$,

$\displaystyle {m\choose 0} 5^{m-1}-{m\choose 1} 5^{m-2}+{m\choose 2} 5^{m-3}-\cdots+{m\choose m-1} $

is not a prime number.

Spoiler

Notice that the given sum can be written as:
$${m\choose m}5^{m-1}-{m\choose m-1} 5^{m-2}+{m\choose m-2} 5^{m-3}-\cdots+{m\choose 1}$$
Since
$$(1+x)^m={m\choose 0}+{m\choose 1}x+{m\choose 2}x^2+\cdots +{m\choose m}x^m$$
$$\Rightarrow \frac{(1+x)^m}{x}=\frac{{m\choose 0}}{x}+{m\choose 1}+{m\choose 2}x+\cdots +{m\choose m}x^{m-1}$$
Substitute $x=-5$ to get,
$${m\choose 1}-{m\choose 2}\cdot 5+\cdots +{m\choose m}5^{m-1}=\frac{1}{5}+\frac{(1-5)^m}{-5}$$
The LHS is the summation (S) given in the question. Hence,
$$S=\frac{4^m+1}{5}=\frac{2^{2m}+1}{5}$$
For odd $m\geq 5$, $2^{2m}$ always ends with unit digit 4, hence, $2^{2m}+1$ is always divisible by 5 which proves that the given summation is not prime.

 

[kaliprasad]

Spoiler

Notice that the given sum can be written as:
$${m\choose m}5^{m-1}-{m\choose m-1} 5^{m-2}+{m\choose m-2} 5^{m-3}-\cdots+{m\choose 1}$$
Since
$$(1+x)^m={m\choose 0}+{m\choose 1}x+{m\choose 2}x^2+\cdots +{m\choose m}x^m$$
$$\Rightarrow \frac{(1+x)^m}{x}=\frac{{m\choose 0}}{x}+{m\choose 1}+{m\choose 2}x+\cdots +{m\choose m}x^{m-1}$$
Substitute $x=-5$ to get,
$${m\choose 1}-{m\choose 2}\cdot 5+\cdots +{m\choose m}5^{m-1}=\frac{1}{5}+\frac{(1-5)^m}{-5}$$
The LHS is the summation (S) given in the question. Hence,
$$S=\frac{4^m+1}{5}=\frac{2^{2m}+1}{5}$$
For odd $m\geq 5$, $2^{2m}$ always ends with unit digit 4, hence, $2^{2m}+1$ is always divisible by 5 which proves that the given summation is not prime.

I beg to disagree

Spoiler

we know 5S = 2^(2m) + 1 is not a prime which is obvious but we need to prove S and not 5S is not prime

 

[Saitama]

I beg to disagree

Spoiler

we know 5S = 2^(2m) + 1 is not a prime which is obvious but we need to prove S and not 5S is not prime

Ah yes, you are right.

 

[kaliprasad]

Spoiler

m is odd

so $2^{2m} + 1 = (2^m)^2 + 1 = (2^m)^2 + 1 + 2 *2^m) - 2 * 2^m)$
= $(2^m + 1)^2 - (2 ^{(m+1)/2})^2$

smaller factor = $2^m - 2^{(m+1)/2} + 1$ ( as m is odd m+1 is even
> 5 for m >= 5 hence it is not prime

 

[Prove It]

It appears that I have misread the original series, hopefully my approach will work with the correct one...

Spoiler

$\displaystyle \begin{align*} S &= \sum_{r = 0}^{m-1}{ {m\choose{r}} 5^{m - r - 1} \left( -1 \right) ^r } \\ 5S &= 5\sum_{r = 0}^{m-1}{ {m\choose{r}} 5^{m-r-1} \left( - 1 \right) ^r } \\ 5S &= \sum_{r = 0}^{m-1}{ {m\choose{r}} 5^{m-r} \left( -1 \right) ^r} \\ 5S - 1 &= \sum_{r = 0}^{m-1} { \left[ {m\choose{r}} 5^{m - r} \left( -1 \right) ^r \right] } - 1 \\ 5S - 1 &= \sum_{r = 0}^{m - 1}{ \left[ {m\choose{r}} 5^{m-r} \left( -1 \right) ^r \right] } + {m\choose{m}}5^0\left( -1 \right) ^m \\ 5S - 1 &= \sum_{r = 0}^m{ {m\choose{r}} 5^{m-r} \left( -1 \right) ^r } \\ 5S- 1 &= \left( 5 - 1 \right) ^m \\ 5S - 1 &= 4^m \\ 5S &= 4^m + 1 \\ S &= \frac{4^m + 1}{5} \end{align*}$

So now we have to prove that $\displaystyle \begin{align*} \frac{4^m + 1}{5} \end{align*}$ is not prime if m is some odd integer greater than or equal to 5. I'm leaning towards induction...

Base step: m = 5

$\displaystyle \begin{align*} \frac{4^5 + 1}{5} &= \frac{1024 + 1}{5} \\ &= \frac{1025}{5} \\ &= 205 \\ &= 5 \cdot 41 \end{align*}$

This is clearly not prime, so the base step is proven.

Now for the inductive step, assume that the statement is true for m = 2k + 1 (where k is another integer $\displaystyle \begin{align*} \geq 2 \end{align*}$, use this to prove the statement is true for m = 2k + 3.

So we assume $\displaystyle \begin{align*} \frac{4^{2k + 1} + 1}{5} \end{align*}$ is not prime, then

$\displaystyle \begin{align*} \frac{4^{2k + 3} + 1}{5} &= \frac{4^2 \cdot 4^{2k + 1} + 1}{5} \\ &= \frac{16 \cdot 4^{2k + 1} + 16 - 15}{5} \\ &= \frac{16 \left( 4^{2k + 1} + 1 \right) - 15}{5} \\ &= 16 \left( \frac{4^{2k + 1} + 1 }{5} \right) - 3 \end{align*}$

I'm still hitting a brick wall, can someone please help me finish?

 

[kaliprasad]

It appears that I have misread the original series, hopefully my approach will work with the correct one...

Spoiler

$\displaystyle \begin{align*} S &= \sum_{r = 0}^{m-1}{ {m\choose{r}} 5^{m - r - 1} \left( -1 \right) ^r } \\ 5S &= 5\sum_{r = 0}^{m-1}{ {m\choose{r}} 5^{m-r-1} \left( - 1 \right) ^r } \\ 5S &= \sum_{r = 0}^{m-1}{ {m\choose{r}} 5^{m-r} \left( -1 \right) ^r} \\ 5S - 1 &= \sum_{r = 0}^{m-1} { \left[ {m\choose{r}} 5^{m - r} \left( -1 \right) ^r \right] } - 1 \\ 5S - 1 &= \sum_{r = 0}^{m - 1}{ \left[ {m\choose{r}} 5^{m-r} \left( -1 \right) ^r \right] } + {m\choose{m}}5^0\left( -1 \right) ^m \\ 5S - 1 &= \sum_{r = 0}^m{ {m\choose{r}} 5^{m-r} \left( -1 \right) ^r } \\ 5S- 1 &= \left( 5 - 1 \right) ^m \\ 5S - 1 &= 4^m \\ 5S &= 4^m + 1 \\ S &= \frac{4^m + 1}{5} \end{align*}$

So now we have to prove that $\displaystyle \begin{align*} \frac{4^m + 1}{5} \end{align*}$ is not prime if m is some odd integer greater than or equal to 5. I'm leaning towards induction...

Base step: m = 5

$\displaystyle \begin{align*} \frac{4^5 + 1}{5} &= \frac{1024 + 1}{5} \\ &= \frac{1025}{5} \\ &= 205 \\ &= 5 \cdot 41 \end{align*}$

This is clearly not prime, so the base step is proven.

Now for the inductive step, assume that the statement is true for m = 2k + 1 (where k is another integer $\displaystyle \begin{align*} \geq 2 \end{align*}$, use this to prove the statement is true for m = 2k + 3.

So we assume $\displaystyle \begin{align*} \frac{4^{2k + 1} + 1}{5} \end{align*}$ is not prime, then

$\displaystyle \begin{align*} \frac{4^{2k + 3} + 1}{5} &= \frac{4^2 \cdot 4^{2k + 1} + 1}{5} \\ &= \frac{16 \cdot 4^{2k + 1} + 16 - 15}{5} \\ &= \frac{16 \left( 4^{2k + 1} + 1 \right) - 15}{5} \\ &= 16 \left( \frac{4^{2k + 1} + 1 }{5} \right) - 3 \end{align*}$

I'm still hitting a brick wall, can someone please help me finish?

I do not think for proving

Spoiler

the number is composite can be proved by Mathemetical induction unless they have same common factor. So factoring is a way out

 

[Prove It]

I do not think for proving

Spoiler

the number is composite can be proved by Mathemetical induction unless they have same common factor. So factoring is a way out

But like you said,

Spoiler

We need a common factor, that means we will need to show that $\displaystyle \begin{align*} \frac{4^{2k+1} + 1}{5} \end{align*}$ is a multiple of 3. Is this possible?

 

[anemone]

Thanks to all who chimed in on this challenge problem.

@kaliprasad, your method is right and correct, well done, kali!

@Pranav, I think we all learn through mistakes, don't we

@Prove It, I don't know if kaliprasad is right or wrong in his judgment that this could not be proved to be right by the induction method, but I hope you will get a definite yes or no soon, either by receiving more convincing replies or by proving it later yourself. :)

 

[kaliprasad]

But like you said,

Spoiler

We need a common factor, that means we will need to show that $\displaystyle \begin{align*} \frac{4^{2k+1} + 1}{5} \end{align*}$ is a multiple of 3. Is this possible?

Spoiler

I do not know why you say multiple of 3. may be it is a typo or a random number but

$(4^5+1)/5$ = 5 * 41
$(4^7+1)/5$ = 29 * 113
$(4^9+1)/5$ = 13 * 37 * 109
and we see that there is no commion factor