# If $m,n\in N$ Prove that there is such a positive integer k, such that $(\sqrt{m}+\sqrt{m+1})^n=\sqrt{k}+\sqrt{k+1}$

If $$m,n\in N$$ Prove that there is such a positive integer k, such that $$(\sqrt{m}+\sqrt{m+1})^n=\sqrt{k}+\sqrt{k+1}$$

I attempted to solve this question using binomial coefficients, saying:

$$(\sqrt{m}+\sqrt{m+1})^n=\sqrt{k}+\sqrt{k+1}=\sum\limits_{a=0}^n {n\choose a}*\sqrt{m}^{n-a}*\sqrt{m+1}^a$$

and from here I was thinking that I had to do something with $$\sqrt{m}^{n-a}$$ with $$\sqrt{k}$$ and do something else with $$\sqrt{k+1}$$ and $$\sqrt{m+1}^a$$. Unfortunately I couldn't think of what to do with this circumstance.

I then thought of maybe taking $$(\sqrt{k}+\sqrt{k+1})^2=(\sum\limits_{a=0}^n {n\choose a}*\sqrt{m}^{n-a}*\sqrt{m+1}^a)^2$$, but this immediately over-complicated the question.

Could you please explain to me how to solve this question and how to solve similar questions in the future?

• @QiaochuYuan I don't see how that (alone) is easily generalizable. Can you continue that train of thought? Jan 3 at 22:14
• @Calvin: hmm, you're right, maybe I spoke too hastily. Jan 3 at 22:16
• Well, if $n =1$ and $k = m$.... Jan 3 at 22:20
• This generalizes the simpler case $m=1$ from this old thread. I think, my solution there would work verbatim, if $m$ were a square. Now we need a bit of extra as in Calvin Lin's solutiion, or split the treatment into even/odd cases like in Neat Math's solution. +1s to all. Jan 3 at 23:03

Let $$x = \sqrt{m+1} + \sqrt{m}$$ and $$y = \sqrt{m+1} - \sqrt{m}$$.

Observe that (IE Fill in the gaps to prove these statements. If you're stuck, explain what you've tried.)

1. $$x \geq 1$$
2. $$xy = 1$$
3. Since $$f(a) = \sqrt{a+1} + \sqrt{a}$$ is strictly increasing with image $$[1, \infty)$$, so there is a unique real (not necessarily integer) $$k_n$$ such that $$x^n = \sqrt{ k_n+1} + \sqrt{k_n}$$. It remains to show that $$k_n$$ is indeed an integer.
4. $$\sqrt{ k_n+1} - \sqrt{k_n} = \frac{1}{ \sqrt{k_n+1} + \sqrt{k_n}} = \frac{1}{x^n} = y^n .$$
5. $$\sqrt{k_n } = \frac{1}{2} (x^n - y^n)$$
6. $$k_n = \frac{1}{4} (x^{2n} + y^{2n} - 2 ) = \frac{1}{2} \left[ -1 + \sum_{i=0}^n {2n \choose 2i}m^i (m+1)^{n-i} \right]$$.
7. Now, show that this is an integer, because the numerator is even.

Consider seperate cases of $$m$$, $$m+1$$ even.
Notice that all but one of the terms in the summation are even.

Notes

• Having read the official solution, I'm amazed this (natural to me) approach worked out so quickly but they didn't use it.
• Defining $$y$$ is pretty natural given $$x$$, and it's a useful trick in such situations. (EG It's also in the official solution.)
• Bonus: $$y^n = \sqrt{ k_n + 1 } -\sqrt{k_n}$$
• $$k_1 = m, k_2 = 4m^2 + 4m, k_3 = 16m^3 + 24m^2 + 9m$$
• I'm slightly amazed that there is a closed form expression for $$k_n$$. I looked at initial $$k_n$$ and couldn't spot a generalizable pattern.
• I very much appreciate your efforts to guide users with observations and hints, and not always straight out answers. For many students, this is more valuable that doing it for them! Thanks! Jan 3 at 22:08
• (+1) Great solution! Jan 3 at 22:08

This is a USAMTS problem. The official solution can be found here. You are actually on the right track.

Below is my solution. Notice that I used the same notation as in the original problem.

My proof:

We prove by induction that: If $$m$$ is odd then $$x^m = a_m\sqrt n + b_m \sqrt{n+1}, na_m^2+1 = (n+1) b_m^2$$ If $$m$$ is even then $$x^m = c_m + d_m \sqrt{n(n+1)}, c_m^2 = n(n+1) d_m^2 +1$$

When $$m=1$$ it's true.

If it's true for $$m$$, we prove it's true for $$m+1$$.

Case 1: If $$m$$ is odd, then $$x^{m+1} = (a_m\sqrt n + b_m \sqrt{n+1}) (\sqrt n + \sqrt{n+1})$$ $$=na_m + (n+1) b_m + (a_m+b_m) \sqrt{n(n+1)}$$ So $$c_{m+1} = na_m+(n+1)b_m, d_{m+1} = (a_m+b_m)$$ and $$c_{m+1}^2-n(n+1)d_{m+1}^2-1$$ $$= n^2 a_m^2 + 2n(n+1)a_mb_m + (n+1)^2b_m^2 - n(n+1)a_m^2 - 2n(n+1)a_mb_m - n(n+1)b_m^2 - 1$$ $$= - n a_m^2+(n+1)b_m^2 - 1 = 0$$ Therefore $$x^{m+1}$$ is groovy.

Case 2: If $$m$$ is even then $$x^{m+1} = (c_m+d_m\sqrt{n(n+1)})(\sqrt n + \sqrt{n+1})$$ $$=(c_m+(n+1)d_m)\sqrt n + (c_m+nd_m)\sqrt{n+1}$$ So $$a_{m+1} = c_m+(n+1)d_m, b_{m+1} = c_m + nd_m$$ and $$na_{m+1}^2+1 - (n+1) b_{m+1}^2$$ $$=nc_m^2+2n(n+1)c_md_m+n(n+1)^2 d_m + 1 - (n+1)c_m^2 - 2n(n+1) c_md_m - (n+1) n^2 d_m^2$$ $$=-c_m^2 + (n+1) d_m^2 + 1=0$$ Again $$x^{m+1}$$ is groovy.

• Very nice observation of how we can calculate the $k_n$. Jan 3 at 21:54