# Thread:

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

please try to solve these questions.
Attached Files
• discrete math.doc (23.5 KB, 56 views)

2. 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

3. 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!

4. 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!

5. ## reply to topsquark

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

6. 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.

7. 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.

8. YOu guys are awesome!!!
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 40, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.878528356552124, "perplexity_flag": "middle"}