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

• Dec 15th 2006, 10:31 PM
m777
induction,irrational and proves......
please try to solve these questions.
• Dec 16th 2006, 05: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 $2n$ where n is some integer. (This is how an even number is defined.) Now square this:
$(2n)^2 = 4n^2 = 2(2n^2)$

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

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

Here's some help . . .

Quote:

Use mathematical induction to prove:
. . $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 $n$.

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

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

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

. . $\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 $S(k+1)$

The right side is: . $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 $S(k+1)$ . . . We're done!

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

Quote:

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

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

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

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

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

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

$\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: . $5^{k+1} - 2^{k+1}$ is divisible by 3 . . . We're done!

• Dec 16th 2006, 05: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, 03:00 PM
ThePerfectHacker
To prove $\sqrt{3}$ is irrational.

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

Prime decompose $a$.
Prime decompose $b$.

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

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

But,
$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, 04:05 PM
Plato
This is a very general proof.
If p is a positive integer that is not a perfect square then $\sqrt p$ is irrational.

Suppose that it is rational, $\sqrt p = \frac{a}{b}$ where a & b are integers.
Let $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:
$\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.$

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

But $K\left( {\sqrt p - \left\lfloor {\sqrt p } \right\rfloor } \right)$ is an integer less than K.
But $\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, 11:30 AM
Judi
YOu guys are awesome!!!