0

If $S=\sum_{1}^{1024}\binom{1024}{k}2^k$, find highest power of $2$ dividing $S$.

I have tried solving using the fact that its equal to $$2^{11} + 2^{2} \binom{1024}{2} + \cdots + 2^{1024}$$ taking $2^{11}$ common we get number to be of form $2^{11}[2k+1]$. So, highest power of $2$ is $11$, but answer is $12$.

What's wrong in my approach?

Blue
  • 75,673
Orion_Pax
  • 431
  • 4
  • 12
  • Note that $\binom {1024}2\times 2^2$ is also $2^{11}$ times an odd number. – lulu Mar 17 '22 at 02:25
  • Easier, I'd say to note that $S=3^{1024}-1$. Then use the factoring $x^{1024}-1=(x-1)(x+1)(x^2+1)(x^4+1)(x^8+1)\cdots (x^{512}+1)$. Here, letting $x=3$, the $x+1$ term yields two factors of $2$ but each of the others yields one. – lulu Mar 17 '22 at 02:27
  • Wow that was very tricky thanks , in general as to avoid mistakes we should do by factorizing only these problems? – Orion_Pax Mar 17 '22 at 02:30
  • Each problem is different. In this case, there was an easily seen factoring available (from the polynomial). This won't always be the case. – lulu Mar 17 '22 at 02:34
  • Understood .... – Orion_Pax Mar 17 '22 at 03:14

1 Answers1

2

You can see that it is at least $12$ as follows: \begin{align} S &= \sum_{k=1}^{1024} \binom{1024}{k}2^k = (1+2)^{1024}-1 = 3^{1024}-1 = (3^{512} + 1)(3^{512} - 1) \\ &= (3^{512} + 1)(3^{256} + 1)(3^{128} + 1)(3^{64} + 1)(3^{32} + 1)(3^{16} + 1)(3^8 + 1)(3^4 + 1)(3^2 + 1)(3 + 1)(3 - 1). \end{align} Now $2$ divides each of these $11$ factors, and $2^2$ divides $(3+1)$, yielding $12$ factors of $2$.

RobPratt
  • 45,619
  • Thanks got it RobPratt , in general we should consider factorization as better method than binomial expansion so as to avoid the mistakes it may cause like this? – Orion_Pax Mar 17 '22 at 02:32
  • Or is there a way to avoid this mistake in binomial too ? – Orion_Pax Mar 17 '22 at 02:32
  • 1
    To see that $12$ is exact, note that none of the terms $3^{2^n}+1$ are divisible by $4$ other than $3+1$. Indeed, $3\equiv -1\pmod 4$ means each of these terms is $2\pmod 4$. – lulu Mar 17 '22 at 02:35
  • Is there a proof of that 3^2^n +1 fact other than checking the numbers ? – Orion_Pax Mar 17 '22 at 03:11
  • It is just repeated use of difference of squares $x^2-1=(x+1)(x-1)$. – RobPratt Mar 17 '22 at 12:00