1
$\begingroup$

Determine all positive integer values of (n) such that

$$ { n \choose 0 } + { n \choose 1 } + { n \choose 2 } + { n \choose 3 } \ \bigg| \ 2 ^ { 2008 } $$

What is the sum of all these values?

CURRENT PROGRESS:

I was able to find out that this is equivalent to $(n+1)(n^2 - n + 6) \,| \,3\times (2)^{2009}$ and opened in 2 cases, $n+1 = 2^a$ and $n+1 = 3\times 2^a$, trying to solve like: $n = 2^a - 1$, then $ n^2 - n + 6 = 2^{2a} - 3\times2^a + 8$, doing the same to the 2nd case but couldn't find solutions. Something that should be useful is that $ n^2 - n + 6 = 2^{2a} - 3\times2^a + 8 | \space\space 3\times2^{2019-a}$, it has a factor 3 in it.

$\endgroup$
  • 1
    $\begingroup$ Note: I reformatted your post fairly heavily. Please check to make sure I didn't change your meaning...your use of "." was hard to interpret in places so I might have misread. $\endgroup$ – lulu Mar 6 at 14:36
  • 1
    $\begingroup$ I saw your changes and then reformatted again to what I meant, thanks $\endgroup$ – Pedro Barros Mar 6 at 14:41
  • $\begingroup$ Welcome to Math.SE. This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc. $\endgroup$ – Carl Mummert Mar 6 at 15:47
  • $\begingroup$ @Carl Mummert, the context of it is that I am studying number theory aiming to perform good classes about this subject for school students. I showed my strategy: Expanding and then opening in two cases that seemed easy to solve but I could not find solutions in it. I am stuck with two equations and probably need restrictions about integers to narrow my search of solutions. $\endgroup$ – Pedro Barros Mar 6 at 16:16
1
$\begingroup$

Set $n+1=m$

$n^2-n+6=(m-1)^2-(m-1)+6=m^2-3m+8$

$g=(m, m^2-3m+8)=(m,8)$

Check all the four possible cases

For example,

If $g=4$

$\dfrac{n+1}4\cdot\dfrac{ n^2-n+6}4$ will divide $3\cdot2^{2008-4}$

where the two factors are relatively prime

i.e. one of the factors must be odd $1$ or $3$

$\endgroup$
  • $\begingroup$ actually you forgot that $-(m-1) = -m + 1$, resulting in:$ m^2 -3m + 8$ $\endgroup$ – Pedro Barros Mar 6 at 15:36
0
$\begingroup$

So $(n+1)(n^2 -n + 6) = 3\cdot 2^{2009}$ so

So $n+1 = 3^t2^s; n^2 -n+6 = 3^r2^w; t+r \le 1; s + w \le 2009$.

Case 1:$t= 0$.

$n = 2^s -1$ and $n^2 - n + 6 = 2^{2s} - 2^{s+1} -2^s + 6$.

If $s = 0$ we have $n=0$ and that's a solution (if we assume ${0\choose k}=0$ for $k \ne 0$). If $s \ge 1$ then

$n^2 -n +6 = 2(2^{2s-1} -2^s - 2^{s-1} + 3)$.

If $s = 1$ we have $n=1$ and that's a solution (if we assume ${n\choose k} = 0$ if $n > k$). If $s \ge 1$ then

$2^{2s-1} - 2^s - 2^{s-1} + 3$ is odd so either is either equal to $3$ or $1$.

So either $2^{2s-1}= 2^s + 2^{s-1}$

$2^{s} = 2 + 1$ which is impossible, or

$2^{2s-1}+2 = 2^s + 2^{s-1}$ so

$2^{2s-2} + 1 = 2^s + 2^{s-2}$ so $s-2 =0$ and $s = 2s -2$ or $s=2$ so $n= 3$ and we have $n+1 = 4$ and $n^2-n+6 = 9$. That's a solution.

So far: $n = 0,n=1, n=3$ are solutions

Case 2: $t = 1$

$n = 3*2^s - 1$ and $n^2 - n + 6 = 9*2^{2s} - 3*2^{s+1} + 1 - 3*2^{s} - 1 + 6 = 3(3*2^{2s} - 2^{s+1} + 2^s + 2) = 2^w$.

That's impossible.

So unless I made a mistake the only solutions are $0, 1,3$ and if we don't consider ${n< k \choose k}$ a legitimate value then the only solution is $n=3$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.