# induction,irrational and proves......

• Dec 15th 2006, 09:31 PM
m777
induction,irrational and proves......
please try to solve these questions.
• Dec 16th 2006, 04:01 AM
topsquark
Quote:

Originally Posted by m777
please try to solve these questions.

1a) What the heck is the definition of Q?

1b) Any even integer is of the form $\displaystyle 2n$ where n is some integer. (This is how an even number is defined.) Now square this:
$\displaystyle (2n)^2 = 4n^2 = 2(2n^2)$

Now, since n is an integer, so is $\displaystyle n^2$. Again, since 2 and [tex]n^2 are integers so is $\displaystyle 2n^2$. Thus $\displaystyle 2(2n^2)$ is an integer it is also an even integer.

-Dan
• Dec 16th 2006, 04:20 AM
Soroban
Hello, m777!

Here's some help . . .

Quote:

Use mathematical induction to prove:
. . $\displaystyle 1 + \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^{n-1}} \;=\;2\left(1 - \frac{1}{2^n}\right)$ for any positive integer $\displaystyle n$.

Verify $\displaystyle S(1)\!:\;1\:=\:2\left(1 - \frac{1}{2}\right) \:=\:1$ . . . true!

Assume $\displaystyle S(k)\!:\;1 + \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^{k-1}} \:=\:2\left(1 - \frac{1}{2^k}\right)$

Add $\displaystyle \frac{1}{2^k}$ to both sides:

. . $\displaystyle \underbrace{1 + \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^{k-1}} + \frac{1}{2^k}} \:=\:2\left(1 - \frac{1}{2^k}\right) + \frac{1}{2^k}$
. . This is the left side of $\displaystyle S(k+1)$

The right side is: .$\displaystyle 2 - \frac{2}{2^k} + \frac{1}{2^k} \;=\;2 - \frac{1}{2^k} \;=\; 2 - \frac{2}{2^{k+1}} \:=\:2\left(1 - \frac{1}{2^{k+1}}\right)$

. . which is the right side of $\displaystyle S(k+1)$ . . . We're done!

• Dec 16th 2006, 04:37 AM
Soroban
Hello again, m777!

Quote:

3) Prove by induction that $\displaystyle 5^n - 2^n$ is divisible by 3.

Verify $\displaystyle S(1)\!:\;5^1 - 2^1 \:=\:3$ is divisible by 3 . . . true!

Assume $\displaystyle S(k)\!:\;5^k - 2^k$ is divisible by 3.
. . Then: .$\displaystyle 5^k - 2^k \;=\;3a$ for some integer $\displaystyle a$.

Add $\displaystyle 4\!\cdot\!5^k - 2^k$ to both sides:

. . $\displaystyle 5^k + 4\!\cdot\!5^k - 2^k - 2^k \;=\;3a + 4\!\cdot\!5^k - 2^k$

We have: .$\displaystyle 5\!\cdot\!5^k - 2\!\cdot\!2^k\;=\;3a + 3\!\cdot\!5^k + 5^k - 2^k$

$\displaystyle \text{Then: }5^{k+1} - 2^{k+1} \;= \;\underbrace{3(a + 5^k)}_{\text{div by 3}} + \underbrace{(5^k - 2^k)}_{\text{div by 3}}$

Therefore: .$\displaystyle 5^{k+1} - 2^{k+1}$ is divisible by 3 . . . We're done!

• Dec 16th 2006, 04:44 AM
m777
Hello,
Topsquark.
In part(a) of question no 1 i have done this so far.
Q(a,b)= o if a<b.
Q(a-b,b)+1 if b is less than equal to a.
so
Q(3,4)=0 SINCE 3<4
GIVEN Q(a,b)= Q(a-b,b)+1) if b is less than equal to a
NOW
Q(14,3)=Q(11,3)+1
=Q(8,3)+1
=Q(5,3)+1
=Q(2,3)+1
SO AT THAT POINT 2 IS LESS THAN 3.
THEREFORE
=0+4
• Dec 16th 2006, 02:00 PM
ThePerfectHacker
To prove $\displaystyle \sqrt{3}$ is irrational.

Assume,
$\displaystyle \sqrt{3}=\frac{a}{b}$
Thus,
$\displaystyle 3=\frac{a^2}{b^2}$
Thus,
$\displaystyle 3b^2=a^2$.

Prime decompose $\displaystyle a$.
Prime decompose $\displaystyle b$.

Note,
$\displaystyle a^2$ has an even number of prime factors.

Note,
$\displaystyle b^2$ has an even number of prime factors.

But,
$\displaystyle 3b^2$ has an odd number of primes factors.

Thus, we have a contradiction because both sides are note equal by the uniquess part of the fundamental theorem of arithmetic.
• Dec 16th 2006, 03:05 PM
Plato
This is a very general proof.
If p is a positive integer that is not a perfect square then $\displaystyle \sqrt p$ is irrational.

Suppose that it is rational, $\displaystyle \sqrt p = \frac{a}{b}$ where a & b are integers.
Let $\displaystyle T = \left\{ {n \in Z^ + :n\sqrt p \in Z^ + } \right\}\quad \Rightarrow \quad b \in T \not= \emptyset.$
By well ordering there is a first term in T, call it K.
Using the floor function and because p is not a square we have the following:
$\displaystyle \left\lfloor {\sqrt p } \right\rfloor < \sqrt p < \left\lfloor {\sqrt p } \right\rfloor + 1\quad \Rightarrow \quad 0 < \sqrt p - \left\lfloor {\sqrt p } \right\rfloor < 1.$

$\displaystyle 0 < K\left( {\sqrt p - \left\lfloor {\sqrt p } \right\rfloor } \right) < K.$

But $\displaystyle K\left( {\sqrt p - \left\lfloor {\sqrt p } \right\rfloor } \right)$ is an integer less than K.
But $\displaystyle \left[ {K\left( {\sqrt p - \left\lfloor {\sqrt p } \right\rfloor } \right)} \right]\sqrt p$ is an integer which contradicts the minimumality of K.
• Dec 18th 2006, 10:30 AM
Judi
YOu guys are awesome!!!