Proof by strong induction of $(a + b\sqrt{2})^n = a_n + b_n \sqrt{2}$

Question

I'm not very familiar with proofs by strong induction. I have a sketch for this one but Iot quite sure about it's validaty.

Let $a$, $b$, $a_n$, $b_n$ be integers such that. $$(a + b\sqrt{2})^n = a_n + b_n \sqrt{2}$$

where $a$ is the integer closest to $b\sqrt{2}$. Prove that $a_n$ is the integer closest to $b_n\sqrt{2}$.

My sketch:

Suppose the statement holds for all $k\le n $ we have to show that it holds for $n+1$

$(a + b\sqrt{2})^n = a_n + b_n \sqrt{2} \Rightarrow$

$ (a + b\sqrt{2})^{n+1} = (a_n + b_n \sqrt{2})(a + b\sqrt{2}) = a a_n + ab_n\sqrt{2} + \sqrt{2} (a_nb + bb_n\sqrt{2}) $

Since $a_n$ is the integer closest to $b_n \sqrt{2}$, $aa_n$ is the integer closest to $ab_n\sqrt{2} $ and $ba_n$ is the integer closest to $b b_n \sqrt{2}$.

My intuition tells that I can prove this with what I wrote, but I can't progress now.

$a a_n + ab_n\sqrt{2} + \sqrt{2} (a_nb + bb_n\sqrt{2})=aa_n+2bb_n+(ab_n+a_nb)\sqrt{2}.$ — mfl, Jul 28 '17 at 13:52
That was my first thought but it seems much more complicated. — João Hiroyuki, Jul 28 '17 at 13:53
I was referring to the Newtons Binomial. Btw, I can't see why $a_{n+1}$ is the integer closest to $b_{n+1}$ as you wrote it. Doesn't seem straightforward to me. — João Hiroyuki, Jul 28 '17 at 14:03
This doesn't appear to be true. For example $(5+ 4\sqrt{2})^2 = 57 + 40\sqrt{2}$. — Michael Lugo, Jul 28 '17 at 14:15
Yeah, actually I forgot to put one term. Sorry, I'm new to Mathjax and I get confused a lot haha — João Hiroyuki, Jul 28 '17 at 14:17
Can you write out "$a$ is the closest integer to $b\sqrt 2$" algebraically? — DanielV, Jul 28 '17 at 16:16

score 2 · Answer 1 · answered Jul 28 '17 at 14:19

2

You don't need "strong induction" for this. The remark $$(a+b\sqrt{2})(c+d\sqrt{2})=(ac+2bd)+(ad+bc)\sqrt{2}$$ provides the induction step in a "weak induction" proof.

answered Jul 28 '17 at 14:19

Christian Blatter

226,825

score 0 · Answer 2 · answered Jul 28 '17 at 17:46

0

Hint. Observe that, if $$ (a+b\sqrt{2})^n=a_n+b_n\sqrt{2}, $$ then (it can be shown inductively) $$ (a-b\sqrt{2})^n=a_n-b_n\sqrt{2}, $$ and if $|a-b\sqrt{2}|<1/2$, then clearly, $(a-b\sqrt{2})^n<1/2$.

answered Jul 28 '17 at 17:46

Yiorgos S. Smyrlis

83,933

Proof by strong induction of $(a + b\sqrt{2})^n = a_n + b_n \sqrt{2}$

2 Answers2