induction,irrational and proves......

**m777** · December 15th 2006, 09:31 PM

please try to solve these questions.

**topsquark** · December 16th 2006, 04:01 AM

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

**Soroban** · December 16th 2006, 04:20 AM

Hello, m777!

Here's some help . . .

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!

**Soroban** · December 16th 2006, 04:37 AM

Hello again, m777!

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!

**m777** · December 16th 2006, 04:44 AM

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
=4 IS THE ANSWER

**ThePerfectHacker** · December 16th 2006, 02:00 PM

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.

**Plato** · December 16th 2006, 03:05 PM

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.

**Judi** · December 18th 2006, 10:30 AM

YOu guys are awesome!!!

Thread: induction,irrational and proves......

LinkBack

Thread Tools

Display

induction,irrational and proves......

reply to topsquark

Similar Math Help Forum Discussions

question on notion of 'proves'...

Proves in Group Theory

Induction on irrational and rational numbers

Discrete Math - Prove that if x is irrational, then 1/x is irrational?

proves -discrete math !!! please help!!!

Search Tags