1

I have to prove that without induction: Let $n$ is non-negative integer number, prove that: $(3+2\sqrt{2})^n=a_n+b_n\sqrt{2}$ where $a_n, b_n$ are positive integer number

My try: $a_1=3, b_1=2$

$a_{n+1}+b_{n+1}\sqrt{2}=(3+2\sqrt2)^{n+1}$

$a_{n+1}+b_{n+1}\sqrt{2}=(a_n+b_n\sqrt{2})(3+2\sqrt{2})$

$a_{n+1}=3a_n+4b_n$

$b_{n+1}=2a_n+3b_n$

Then I don't know how to prove that without induction. Thanks for help!

Zain Patel
  • 16,802
evyz
  • 11
  • 2
    Recall Binomial theorem? Try combining even and odd terms. (of course, the proof of binomial theorem uses induction!) – Raghav Dec 02 '13 at 17:18
  • 1
    $3+2\sqrt{2} = (1+\sqrt{2})^2$ – chatur Dec 02 '13 at 17:20
  • 1
    As my professor would say: you cannot prove something like this without induction, you will always have implicit induction. – Sid Dec 02 '13 at 17:23
  • You can compute $(3+2\sqrt{2})^n$ for each value of $n$. That would prove it, for as many $n$'s you manage to compute, without induction. – OR. Dec 02 '13 at 17:25
  • $3+2\sqrt{2} = (1+\sqrt{2})^2$ so that,$(1+\sqrt{2})^{2n} = \sum^{i=2n}{i=0} C^(2n){i} 1^{2n-i}(\sqrt{2})^(i)$, every term is of the form $l_n+\sqrt{2}m_n$ hence their sum is also of the form $a_n + b_n$ – chatur Dec 02 '13 at 17:26
  • Note that same do not hold for $(1+ 2^{\frac{1}{4}})^n$. i.e. sum is not of the form $a_n + b_n 2^{\frac{1}{4}}$ but is $a_n + b_n 2^{\frac{1}{4}} + c_n\sqrt{2}$ – chatur Dec 02 '13 at 17:31
  • @ABC I believe the idea is that induction is used when it comes to Peano's axioms. If you use a different axiomatic system for the natural numbers, induction will presumably also be involved. – Sid Dec 02 '13 at 17:34
  • Your statement is not true for $n=0$ because $b_0=0$, which is not positive. But this is tiny point. – Henry Dec 02 '13 at 17:45

4 Answers4

4

$$\left(k+l\sqrt2\right)\left(m+n\sqrt2\right) = (km+2ln) + (kn+lm)\sqrt2$$

so terms of the form $a+b\sqrt2$ with $a,b$ positive integers are closed under multiplication and thus under positive integer powers.

Moving from multiplication to positive integer powers may involve an implicit induction: I suspect that this is unavoidable if you want your statement to be true for all positive integer $n$.

Henry
  • 157,058
2

$$(3+2\sqrt{2})^n=\sum_{k=0}^n\binom{n}{k}3^{n-k}2^k(\sqrt2)^k=$$ $$=\sum_{j=0}^{n/2}\binom{n}{2j}3^{n-2j}2^{2j}(\sqrt2)^{2j}+\sum_{i=0}^{n/2}\binom{n}{2i+1}3^{n-2i-1}2^{2i+1}(\sqrt2)^{2i+1}=$$ $$=\sum_{i=0}^{n/2}\binom{n}{2i+1}3^{n-2i-1}2^{2i+1}2^i\sqrt2+\sum_{j=0}^{n/2}\binom{n}{2j}3^{n-2j}2^{2j}2^{j}=$$ $$=\sum_{j=0}^{n/2}\binom{n}{2j}3^{n-2j}2^{3j}+\sum_{i=0}^{n/2}\binom{n}{2i+1}3^{n-2i-1}2^{3i+1}\sqrt2$$ $$a_n=\sum_{j=0}^{n/2}\binom{n}{2j}3^{n-2j}2^{3j}$$ $$b_n=\sum_{i=0}^{n/2}\binom{n}{2i+1}3^{n-2i-1}2^{3i+1}$$

Adi Dani
  • 16,949
0

Let's prove the stronger claim that $a_n,b_n \in \mathbb{Z^+}$ and ${a_n}^2 - 2{b_n}^2 = 1$. So $\lim\limits_{n \rightarrow \infty}{\dfrac{a_n}{b_n}} = \sqrt{2}$ among other things.

Using the binomial theorem* you can establish that $(3 - 2\sqrt2)^n = a_n - b_n\sqrt2$ as $\sqrt2$ terms arise from odd powers of $(-2\sqrt2)$. These always have a negative sign.

* Pertinent to the the binomial theorem:

  • The binomial theorem can be proved combinatorially. See Combinatorial Proof of Multinomial Theorem - Without Induction or Binomial Theorem.
  • All powers of $3$ and all even powers of $2\sqrt2$ in expansions of both $(3+2\sqrt2)^n\text{ and }(3-2\sqrt2)^n$ are whole numbers. Likewise, odd powers of $2\sqrt2$ are whole multiples of $\sqrt2$.
  • For positive integer exponents, all binomial coefficients are whole numbers (combinatorial combinations)

Then you have (for some $a_n, b_n$ which are integers by the above):

$\begin{align} (3+2\sqrt{2})^n&=a_n+b_n\sqrt{2} \\ (3-2\sqrt{2})^n&=a_n-b_n\sqrt{2} \end{align}$

which solves to (including the case $n=1$)

$a_n = \dfrac{1}{2}[(3+2\sqrt2)^n+(3-2\sqrt2)^n] \tag{1}$

$b_n = \dfrac{1}{2\sqrt2}[(3+2\sqrt2)^n-(3-2\sqrt2)^n] \tag{2}$

Now $(3+2\sqrt2) > (3-2\sqrt2) > 0 \implies (3+2\sqrt2)^n > (3-2\sqrt2)^n > 0$, so both $a_n, b_n \ge 1$.

With these expressions for $a_n, b_n$, we can compute

$\begin{align} {a_n}^2-2{b_n}^2 &= \dfrac{1}{4}[(3+2\sqrt2)^{2n}+2+(3-2\sqrt2)^{2n}] - 2\times\dfrac{1}{8}[(3+2\sqrt2)^{2n}-2+(3-2\sqrt2)^{2n}] \\ &= \frac{1}{2} + \frac{1}{2} \\ &= 1 \end{align}$

which is therefore an identity for all $n \in \mathbb{Z^+}$.

Community
  • 1
Marconius
  • 5,635
0

Note that $$ \big( 2 \sqrt{2} + 3 \big) = \big(\sqrt{2} + 1\big)^2. $$

First we construct a recursion relation by using $$ \big( \sqrt{2} + 1 \big) \big( p_n \sqrt{2} + q_n \big) = \big( \underbrace{p_n + q_n}_{\displaystyle p_{n+1}} \big) \sqrt{2} + \big(\underbrace{2 p + q }_{\displaystyle q_{n+1}} \big). $$ Whence $$ \left[ \begin{array}{rcl} p_{n+1} &=& p_n + q_n\\ q_{n+1} &=& 2 p_n + q_n \end{array} \right. $$ Therefore $$ p_{n+2} = 2 p_{n+1} + p_{n}, \hspace{2em} q_{n} = p_{n+1} - p_{n} $$ This is a brother of Fibonacci :)

We obtain the $\phi$ equation $$ \phi^2 = 2 \phi + 1 \Rightarrow \phi_\pm = 1 \pm \sqrt{2}. $$ And we obtain the solutions $$ p_n = \frac{\phi_+^n - \phi_-^n}{\phi_+ - \phi_-}, \hspace{2em} q_n = \frac{\phi_+^n + \phi_-^n}{\phi_+ - \phi_-} \sqrt{2}. $$ So we obtain $$ \big( \sqrt{2} + 1 \big)^n = \frac{\big(1+\sqrt{2})^n - \big(1-\sqrt{2})^n}{2\sqrt{2}} \sqrt{2} + \frac{\big(1+\sqrt{2})^n + \big(1-\sqrt{2})^n}{2}. $$

The final result is $$ \big( 2 \sqrt{2} + 3 \big)^n = \frac{\big(3+2\sqrt{2})^n - \big(3-2\sqrt{2})^n}{2\sqrt{2}} \sqrt{2} + \frac{\big(3+2\sqrt{2})^n + \big(3-2\sqrt{2})^n}{2}. $$

johannesvalks
  • 6,407