Suppose $$\sum_{k\ {\rm odd}}^n {n \choose k} 2^{(k-1)/2} = \sum_{k\ {\rm odd}}^m {m \choose k} 2^{(k-1)/2} 3^{(m-k)/2}.$$ Does $m=n=1$?

Clearly $m \leq n$, and for every $n$ there is at most one $m$.


Here we find a closed expression for the series and show that a solution with $m$ even is not possible.

We use the convention $\binom{n}{k}=0$ if $0\leq n < k$ and start with the left-hand side. We obtain \begin{align*} \sum_{k\ {\rm odd}}^n {n \choose k} 2^{(k-1)/2}&= \sum_{k=0}^n \binom{n}{2k+1} 2^k\tag{1}\\ &=\frac{1}{\sqrt{2}}\sum_{k=0}^n\binom{n}{2k+1}\left(\sqrt{2}\right)^{2k+1}\tag{2}\\ \end{align*}


  • In (1) we replace $k$ with $2k+1$ in the summands without changing anything since we add only zeros.

  • In (2) we do a rearrangement which is helpful for further steps.

We consider

\begin{align*} f(x)=\sum_{k=0}^n\binom{n}{k}x^k=(1+x)^n \end{align*} and get the odd part of $f(x)$ via \begin{align*} \frac{1}{2}\left(f(x)-f(-x)\right)=\sum_{k=0}^n\binom{n}{2k+1}x^{2k+1} \end{align*}

We obtain from (2) \begin{align*} \sum_{k\ {\rm odd}}^n {n \choose k} 2^{(k-1)/2}&=\frac{1}{2\sqrt{2}}\left(f(\sqrt{2})-f(-\sqrt{2})\right)\\ &=\frac{1}{2\sqrt{2}}\left(\left(1+\sqrt{2}\right)^n-\left(1-\sqrt{2}\right)^n\right)\tag{3} \end{align*}

Similarly we can transform the right-hand side:

\begin{align*} \sum_{k\ {\rm odd}}^m {m \choose k} 2^{(k-1)/2} 3^{(m-k)/2}&=3^{(m-1)/2}\sum_{k\ {\rm odd}}^m {m \choose k} \left(\frac{2}{3}\right)^{(k-1)/2}\\ &=3^{m/2}\frac{1}{2\sqrt{2}}\left(f\left(\sqrt{\frac{2}{3}}\right) -f\left(-\sqrt{\frac{2}{3}}\right)\right)\\ &=3^{m/2}\frac{1}{2\sqrt{2}}\left(\left(1+\sqrt{\frac{2}{3}}\right)^m-\left(1-\sqrt{\frac{2}{3}}\right)^m\right)\\ &=\frac{1}{2\sqrt{2}}\left(\sqrt{3}+\sqrt{2}\right)^m-\left(\sqrt{3}-\sqrt{2}\right)^m\tag{4} \end{align*}

We conclude from (3) and (4) OPs equation is equivalent with

\begin{align*} \left(1+\sqrt{2}\right)^n-\left(1-\sqrt{2}\right)^n =\left(\sqrt{3}+\sqrt{2}\right)^m-\left(\sqrt{3}-\sqrt{2}\right)^m\tag{5} \end{align*}

In case $m=n=1$ we obtain \begin{align*} \left(1+\sqrt{2}\right)-\left(1-\sqrt{2}\right)&=2\sqrt{2}\\ \\ \left(\sqrt{3}+\sqrt{2}\right)-\left(\sqrt{3}-\sqrt{2}\right)&=2\sqrt{2} \end{align*} and equality holds.

The left-hand side of (5) has the representation \begin{align*} \left(1+\sqrt{2}\right)^n&-\left(1-\sqrt{2}\right)^n\\ &=\sum_{k=0}^n\binom{n}{k}\left(\sqrt{2}\right)^k-\sum_{k=0}^n\binom{n}{k}(-1)^k\left(\sqrt{2}\right)^k\tag{6}\\ &=A\sqrt{2}\qquad\qquad \text{ with }A\in\mathbb{N} \end{align*}

Since odd $k$ only provide contributions to the expression in (6) we observe that the resulting value is an integer multiple of $\sqrt{2}$.

The right-hand side has the representation \begin{align*} \left(\sqrt{3}+\sqrt{2}\right)^n&-\left(\sqrt{3}-\sqrt{2}\right)^n\\ &=\sum_{k=0}^n\binom{n}{k}\left(\sqrt{2}\right)^k\left(\sqrt{3}\right)^{n-k} -\sum_{k=0}^n\binom{n}{k}(-1)^k\left(\sqrt{2}\right)^k\left(\sqrt{3}\right)^{n-k}\tag{7}\\ &= \begin{cases} B\sqrt{2}\qquad\qquad &\text{ with }B\in\mathbb{N} \text { if } n \text { is odd}\\ C\sqrt{6}\qquad\qquad &\text{ with }C\in\mathbb{N} \text { if } n \text { is even}\\ \end{cases} \end{align*}

Again odd $k$ only provide contributions to the expression in (7). If $n$ is odd, $n-k$ is even and the resulting value is an integer multiple of $\sqrt{2}$. Otherwise, if $n$ is even we get additionally a factor $\sqrt{3}$ resulting in an integer multiple of $\sqrt{6}$.

Conclusion: OPs equation is not valid if $m$ is even.

The case $m$ odd needs further investigations.

  • $\begingroup$ Maybe I'm dense in the real numbers, but I don't see how I can finish the argument. (The RHS can also be written in terms of $\sqrt{2} \pm \sqrt{3}$. Did you take out the $3^{m/2}$ on purpose?) $\endgroup$ – Ricardo Buring May 18 '16 at 17:01
  • $\begingroup$ @RicardoBuring: I took out $m^{3/2}$ just to be able to apply the odd part of $f(x)$ as I did in (2). Updated it accordingly. Regards, $\endgroup$ – Markus Scheuer May 18 '16 at 17:33


Your equation only has finite number of solutions, but in order to check whether $m=n=1$ is the unique solution, you would need some numerical verification and the existing bounds might not be sufficiently effective.

Relevant references:

  1. M. Laurent. Équations exponentielles polynômes et suites récurrentes linéaires. Astérisque 147–148 (1987), 121–139.
  2. H. P. Schlickewei and W. Schmidt. Linear equations in members of recurrence sequences. Ann. Scuola Norm. Sup. Pisa Cl. Sci. 20 (1993), 219–246.
  3. H. P. Schlickewei and W. Schmidt. The intersection of recurrence sequences. Acta Arith. 72 (1995), 1–44.

The equivalence of your problem to finding intersections of two linear recursive sequences $u_n=v_p$, where $p=2m+1$ and

$u_{n+1}=2u_{n}+u_{n-1}$, with $u_0=0$, $u_1=1$;

$v_{p+1}=10v_{p}-v_{p-1}$, with $v_0=1$, $v_1=11$,

can be seen by either directly using the original representation in sum or using the closed-form solutions in Markus Scheuer’s answer.

This set-up has been studied in much greater generality in the reference above. Since $u$ and $v$ are not related, there are only finite solutions. There is some bound of the size of the solutions in 3 but I am not sure how effective they are. You might want to go through more recent work, e.g.,

  1. M. Bennett and P. Ákos. Intersections of recurrence sequences. Proceedings of the American Mathematical Society 143, no. 6 (2015), 2347-2353.

to see if any improvement has been developed.


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.