Prove that $(n+\sqrt{n^2 -1})^k$ will always be of the form$(t+\sqrt{t^2 -1})$ where $n$, $k$, $t$ are natural numbers

Show that $(n+\sqrt{n^2 -1})^k$ will always be of the form$(t+\sqrt{t^2 -1})$ where $n$, $k$, $t$ are natural numbers

-
What have you tried? –  Mark Bennet Aug 3 '12 at 8:30
Try to prove it by induction –  Norbert Aug 3 '12 at 8:56
$(2+\sqrt3)^1 = (2+\sqrt[]{2^2-1})$ –  Rajesh K Singh Aug 3 '12 at 9:00
$(3+\sqrt8)^1=(3+\sqrt[]{3^2-1})$,$(3+\sqrt8)^2=(17+\sqrt[]{17^2-1})$ –  Rajesh K Singh Aug 3 '12 at 9:03
It would be useful to know some context, and whether this is homework, and where the problem comes from and why it is interesting. There is a neat way of looking at this, but it would be a shame to be given a 'magic' solution out of context because you won't then be able to apply the same idea to a different problem. –  Mark Bennet Aug 3 '12 at 9:04

I enjoyed working this out-cool question man. Here's a straightforward inductive proof:

I'm writing $c$ instead of $n$.

Inductively assume $(c + \sqrt{c^2 - 1})^k = a + b \sqrt{c^2 - 1}$, where $b^2(c^2 - 1) = a^2 - 1$ (the base case is clear). That is, not only can you write it as $t + \sqrt{t^2 - 1}$, but also $t^2 - 1$ is a square times $c^2 - 1$ (I guessed this by working out the first $k$'s for $c =2,3$).

Now to see $k \Rightarrow k+1$, we have $$(c + \sqrt{c^2 - 1})^{k+1} = (a + b \sqrt{c^2 - 1})(c + \sqrt{c^2 - 1})$$$$= (ac + b(c^2 - 1)) + (a + cb)\sqrt{c^2 - 1}$$It suffices to check that $$(ac + b(c^2 - 1))^2 - 1 = (a + cb)^2(c^2 - 1)$$Expanding both sides gives $$c^2 a^2 + 2c(c^2 - 1)ab + (c^2 - 1)^2 b^2 - 1 = (c^2 - 1)a^2 + 2c(c^2 - 1)ab + c^2(c^2 - 1)b^2$$Cancelling the $ab$ terms, pulling the $a^2$ term to the LHS, and the $b^2$ terms to the RHS, we get $$a^2 - 1=b^2(c^2 - 1)$$our inductive hypothesis.

-
thanks for the hints. –  Rajesh K Singh Aug 3 '12 at 14:09
is it square times $b\sqrt[]{c^2-1}$ –  Rajesh K Singh Aug 3 '12 at 14:39
hmm, I guess mean that $\sqrt{t^2 - 1}$ can always be simplified to $b \sqrt{c^2 - 1}$, i.e. that $t^2 - 1 = b^2(c^2 - 1)$. For example, as you computed, for powers of $(2 + \sqrt{3})$, for $k=2$ you get $7 + 4\sqrt{3} = 7 + \sqrt{7^2 - 1}$, and for $k=3$ you get $26 + 15\sqrt{3} = 26 + \sqrt{26^2 - 1}$ –  uncookedfalcon Aug 3 '12 at 21:37

Let $\sqrt {n^2-1}=\alpha$

Then $(n+\alpha)(n-\alpha)=1$ and it is easy to see (prove by induction) that $(n+\alpha)^k = t+u\alpha \text{ and } (n-\alpha)^k = t-u\alpha$ with $t$ and $u$ integers so: $$1=(n+\alpha)^k(n-\alpha)^k = (t+u\alpha)(t-u\alpha)= t^2-u^2\alpha^2$$

So $$u\alpha = \sqrt{t^2-1} \text{ and } (n+\alpha)^k=t+\sqrt{t^2-1}$$

-
thanks for the clue –  Rajesh K Singh Aug 3 '12 at 14:10

First of all, notice that if $n$ is an integer and $a = n + \sqrt{n^2-1}$, then $n = \frac{1}{2}(a+\frac{1}{a})$. Next notice that the direction of implication can be reversed here, i.e. if $\frac{1}{2}(a+\frac{1}{a})$ is an integer then a can be written in the form $n + \sqrt{n^2-1}$ where $n$ is an integer by setting $n = \frac{1}{2}(a+\frac{1}{a})$.

With this in mind, we simply have to prove that if $\frac{1}{2}(a+\frac{1}{a})$ is an integer then so is $\frac{1}{2}(a^k+\frac{1}{a^k})$ for any integer $k$. This can be easily seen by induction on $k$ using the binomial expansion of $(a+\frac{1}{a})^k$ and the symmetry of the binomial coefficients.

EDIT:

To clarify the second part, $$\left(a+\frac{1}{a}\right)^k = \left(a^k+\frac{1}{a^k}\right) + \sum_{i=1}^{\lfloor{k/2}\rfloor}{k \choose i} + (\text{if k even}){k \choose k/2}$$

LHS is $k$th power of even number so even. All but first term in RHS are even (by induction hypothesis and fact that central binomial coefficient is even). So $(a^k+\frac{1}{a^k})$ must also be even.

-

The roots of $x+\frac1x=2n$ are $x_n=n+\sqrt{n^2-1}$ and $1/x_n=n-\sqrt{n^2-1}$.

If we can show that $$x_n^k+1/x_n^k=2m_{n,k}\tag{1}$$ (that is, an even integer), then we get the form we want: $$x_n^k=m_{n,k}+\sqrt{m_{n,k}^2-1}\tag{2}$$ Initial Case: for $k=1$, obviously, $x_n^1+1/x_n^1=2n$.

Inductive Case: suppose that $(1)$ holds for all $j<k$, that is, $x_n^j+1/x_n^j=2m_{n,j}$. Then, \begin{align} (2n)^k &=\left(x_n+1/x_n\right)^k\\ &=x_n^k+1/x_n^k+\sum_{j=1}^{k-1}\binom{k}{j}x_n^{k-2j}\\ &=x_n^k+1/x_n^k+\left\{\begin{array}{} \binom{k}{k/2}+\sum_{j=1}^{k/2-1}\binom{k}{j}(x_n^{k-2j}+1/x_n^{k-2j})&\mbox{if k is even}\\ \sum_{j=1}^{(k-1)/2}\binom{k}{j}(x_n^{k-2j}+1/x_n^{k-2j})&\mbox{if k is odd} \end{array}\right.\\ &=x_n^k+1/x_n^k+\left\{\begin{array}{} \binom{k}{k/2}+2\sum_{j=1}^{k/2-1}\binom{k}{j}m_{n,k-2j}&\mbox{if k is even}\\ 2\sum_{j=1}^{(k-1)/2}\binom{k}{j}m_{n,k-2j}&\mbox{if k is odd} \end{array}\right.\tag{3} \end{align} When $k$ is even, $\binom{k}{k/2}$ has as many factors of $2$ as there are $1$-bits in the binary representation of $k$ (that is, at least $1$). Therefore, since $(2n)^k$, $\binom{k}{k/2}$ (if $k$ is even), and $2\sum\binom{k}{j}m_{n,k-2j}$ are all even, $(3)$ says that $x_n^k+1/x_n^k$ is even, which validates $(1)$.

Recursion for $m_{n,k}$:

Start with $m_{n,1}=n$, then $$m_{n,k}=2^{k-1}n^k-\left\{\begin{array}{} \frac12\binom{k}{k/2}+\sum_{j=1}^{k/2-1}\binom{k}{j}m_{n,k-2j}&\mbox{if k is even}\\ \sum_{j=1}^{(k-1)/2}\binom{k}{j}m_{n,k-2j}&\mbox{if k is odd} \end{array}\right.$$

-

Hint $\rm\ \alpha = n\! +\! \sqrt{n^2\!-\!1}\:$ has norm $\rm\,N(\alpha) = \alpha\alpha' = n^2\!-(n^2\!-\!1) = 1,\:$ so $\rm\:N(\alpha^n) = N(\alpha)^n = 1.\:$

Conversely, quadratic numbers of norm $1$ have this form: $\rm\: 1 = (a\!+\!bw)(a\!-\!bw) = a^2\! -\! b^2 w^2,\:$ so $\rm\: b^2 w^2 = a^2\!-\!1\:\Rightarrow\: bw = \sqrt{a^2\!-\!1}\:\Rightarrow\:a+bw = a+\sqrt{a^2-1},\:$ by $\rm\:w^2 > 0,\,$ and wlog $\rm\,b\ge 0.$

-

Let, $$f(k)=(2+\sqrt[]{2^2-1})^k$$ -------(1)

consider $k=1$

$$f(1)=(2+\sqrt[]{2^2-1})^1$$

i.e. $$f(1)=(2+\sqrt[]{2^2-1})=\frac{1}{2-\sqrt[]{2^2-1}}$$

consider $k=2$

$$f(2)=(2+\sqrt[]{2^2-1})^2$$

i.e. $$f(2)=(4+(2^2-1)+4\sqrt[]{2^2-1})$$

i.e. $$f(2)=(7+4\sqrt[]{2^2-1})$$

i.e. $$f(2)=(7+\sqrt[]{(4^2)(2^2-1)})$$

i.e. $$f(2)=(7+\sqrt[]{7^2-1})=\frac{1}{7-\sqrt[]{7^2-1}}$$ Assume $f(n)$ holds for $k=n$

i.e. $$f(n)=(2+\sqrt[]{2^2-1})^n=(t+\sqrt[]{t^2-1})=(a+b\sqrt[]{3})$$ -------(2)

where a and b are natural numbers

i.e. $$f(n)=(2+\sqrt[]{2^2-1})^n=(t+\sqrt[]{t^2-1})=(a+\sqrt[]{3b^2})$$

for the assumption to hold, $$3b^2 = a^2-1$$ -------(3)

consider $k=n+1$

i.e. $$f(n+1)=(2+\sqrt[]{2^2-1})^{n+1}=(t+\sqrt[]{t^2-1})(2+\sqrt[]{2^2-1})$$

we also have, $$f(n+1) =(a+b\sqrt[]{3})(2+\sqrt[]{3})$$

where a and b are natural numbers

i.e. $$f(n+1)=(2a+3b)+(a+2b)\sqrt[]{3}$$ -------(4)

i.e. $$f(n+1)=(2a+3b)+\sqrt[]{3(a+2b)^2}$$

i.e. $$f(n+1)=(2a+3b)+\sqrt[]{3(a^2+4b^2+4ab)}$$

i.e. $$f(n+1)=(2a+3b)+\sqrt[]{3a^2+12b^2+12ab)}$$

i.e. $$f(n+1)=(2a+3b)+\sqrt[]{3a^2+12b^2+12ab + (a^2-a^2) + (3b^2-3b^2)}$$ -------(5)

i.e. $$f(n+1)=(2a+3b)+\sqrt[]{(3a^2+12b^2+12ab +a^2) -a^2 + (3b^2-3b^2)}$$

i.e. $$f(n+1)=(2a+3b)+\sqrt[]{(4a^2+12b^2+12ab) + (3b^2-3b^2) -a^2}$$

i.e. $$f(n+1)=(2a+3b)+\sqrt[]{(4a^2+12b^2+12ab) + (-3b^2+3b^2) -a^2}$$

i.e. $$f(n+1)=(2a+3b)+\sqrt[]{(4a^2+12b^2+12ab -3b^2) +3b^2 -a^2}$$

i.e. $$f(n+1)=(2a+3b)+\sqrt[]{(4a^2+9b^2+12ab) + (3b^2 -a^2)}$$

i.e. $$f(n+1)=(2a+3b)+\sqrt[]{(2a+3b)^2 + (3b^2 -a^2)}$$ -------(6)

by careful observation, using expressions (3) and (6) we have $$f(n+1)=(2a+3b)+\sqrt[]{(2a+3b)^2 + (a^2 -1 -a^2)}$$

i.e. $$f(n+1)=(2a+3b)+\sqrt[]{(2a+3b)^2 -1 + (a^2-a^2)}$$

i.e. $$f(n+1)=(2a+3b)+\sqrt[]{(2a+3b)^2 -1}$$ which is indeed of the form $$f(n+1)=(t+\sqrt[]{t^2-1})$$ where $t=(2a+3b)$

-
yeah man exactly! (well, I didn't check all the steps, but I think your argument is what I was thinking as well) –  uncookedfalcon Aug 3 '12 at 21:39