Four mathematical induction problems

**rectangle** · October 31st 2010, 11:32 AM

Hi...
I have an exam soon, and didn't succeed to prove those...

Thank you so much!!!

**Archie Meade** · October 31st 2010, 12:28 PM

Originally Posted by rectangle

Hi...
I have an exam soon, and didn't succeed to prove these...

Thank you so much!!!

For 1.

P(k)

$\displaystyle\ 1+\frac{1}{\sqrt{2}}+....+\frac{1}{\sqrt{k}}>\sqrt {k}$

P(k+1)

$\displaystyle\ 1+\frac{1}{\sqrt{2}}+....+\frac{1}{\sqrt{k+1}}>\sq rt{k+1}$

Show that "if" P(k) is valid, then P(k+1) "must therefore" also be valid.
Hence, write P(k+1) in terms of P(k).

Proof

If P(k) is valid, then

$\displaystyle\ 1+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{k}}+\frac{ 1}{\sqrt{k+1}}>\sqrt{k}+\frac{1}{\sqrt{k+1}}$

If $\displaystyle\ \sqrt{k}+\frac{1}{\sqrt{k+1}}>\sqrt{k+1}$ , then P(k+1) will be valid.

$\displaystyle\ \sqrt{k}+\frac{1}{\sqrt{k+1}}=\frac{\sqrt{k+1}\sqr t{k}+1}{\sqrt{k+1}}$

If $\displaystyle\frac{\sqrt{k+1}\sqrt{k}+1}{\sqrt{k+1 }}>\sqrt{k+1}$

then

$\displaystyle\sqrt{k+1}\sqrt{k}+1>k+1$

It can be seen that this is true since $\sqrt{k+1}>\sqrt{k}$

hence, you need to examine the case for $n=2.$

**rectangle** · November 1st 2010, 01:20 AM

Originally Posted by Archie Meade

For 1.

P(k)

$\displaystyle\ 1+\frac{1}{\sqrt{2}}+....+\frac{1}{\sqrt{k}}>\sqrt {k}$

P(k+1)

$\displaystyle\ 1+\frac{1}{\sqrt{2}}+....+\frac{1}{\sqrt{k+1}}>\sq rt{k+1}$

Show that "if" P(k) is valid, then P(k+1) "must therefore" also be valid.
Hence, write P(k+1) in terms of P(k).

Proof

If P(k) is valid, then

$\displaystyle\ 1+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{k}}+\frac{ 1}{\sqrt{k+1}}>\sqrt{k}+\frac{1}{\sqrt{k+1}}$

If $\displaystyle\ \sqrt{k}+\frac{1}{\sqrt{k+1}}>\sqrt{k+1}$ , then P(k+1) will be valid.

$\displaystyle\ \sqrt{k}+\frac{1}{\sqrt{k+1}}=\frac{\sqrt{k+1}\sqr t{k}+1}{\sqrt{k+1}}$

If $\displaystyle\frac{\sqrt{k+1}\sqrt{k}+1}{\sqrt{k+1 }}>\sqrt{k+1}$

then

$\displaystyle\sqrt{k+1}\sqrt{k}+1>k+1$

It can be seen that this is true since $\sqrt{k+1}>\sqrt{k}$

hence, you need to examine the case for $n=2.$

Thank you very much!

**Archie Meade** · November 1st 2010, 07:29 AM

For 2.

$\displaystyle\sqrt{a+\sqrt{a+\sqrt{a+....}}}\le\ \frac{1+\sqrt{4a+1}}{2}$

You want to show that this inequality holds true for any level of nesting.
Suppose the above inequality is at a nesting depth of $n$ or $k$

P(k)

$\displaystyle\sqrt{a+\sqrt{a+\sqrt{a+....}}}\le\ \frac{1+\sqrt{4a+1}}{2}$

for a nesting depth of k.

Add $a$ to both sides and take the square root to get a depth of $k+1.$

$a+\displaystyle\sqrt{a+\sqrt{a+\sqrt{a+....}}}\le\ a+\frac{1+\sqrt{4a+1}}{2}$

$\displaystyle\sqrt{a+\sqrt{a+\sqrt{a+\sqrt{a+....} }}}\le\ \sqrt{a+\frac{1+\sqrt{4a+1}}{2}}$

The above has a nesting depth of $k+1.$

P(k) will definately be valid if $\displaystyle\sqrt{\frac{2a+1+\sqrt{4a+1}}{2}}\le\ \frac{1+\sqrt{4a+1}}{2}$

If this is so, then P(k) is always true.

Squaring both sides...

$\displaystyle\frac{2a+1+\sqrt{4a+1}}{2}\le\frac{1+ 2\sqrt{4a+1}+4a+1}{4}$ ??

It's now a simple matter to verify this.

Finally, test for $n=1$ or $k=1..$

$\displaystyle\sqrt{a}\le\ \frac{1+\sqrt{4a+1}}{2}$ ?

$2\sqrt{a}\le\ 1+\sqrt{4a+1}$ ?

$\sqrt{4a}\le\ 1+\sqrt{4a+1}$

which is certainly true as $\sqrt{4a+1}>\sqrt{4a}$

**Archie Meade** · November 1st 2010, 02:20 PM

No.3 is straightforward.

For $x_k>0,$ prove by induction that

$\left(x_1+x_2+.....+x_n\right)\left(\frac{1}{x_1}+ \frac{1}{x_2}+....+\frac{1}{x_n}\right)\ \ge\ n$

P(k)

$\left(x_1+x_2+.....+x_k\right)\left(\frac{1}{x_1}+ \frac{1}{x_2}+....+\frac{1}{x_k}\right)\ \ge\ k$

P(k+1)

$\left(x_1+x_2+.....+x_k+x_{k+1}\right)\left(\frac{ 1}{x_1}+\frac{1}{x_2}+....+\frac{1}{x_k}+\frac{1}{ x_{k+1}}\right)\ \ge\ k+1$

Try to show that if P(k) is true, then it causes P(k+1) to also be true.

Proof

$\left(x_1+.....+x_k+x_{k+1}\right)\left(\frac{1}{x _1}+....+\frac{1}{x_k}+\frac{1}{x_{k+1}}\right)=$

$\left(x_1+.....+x_k\right)\left(\frac{1}{x_1}+.... +\frac{1}{x_k}+\frac{1}{x_{k+1}}\right)+x_{k+1}\le ft(\frac{1}{x_1}+....+\frac{1}{x_k}+\frac{1}{x_{k+ 1}}\right)=$

$\left(x_1+.....+x_k\right)\left(\frac{1}{x_1}+.... +\frac{1}{x_k}\right)+\left(x_1+....+x_k}\right)\l eft(\frac{1}{x_{k+1}}\right)+x_{k+1}\left(\frac{1} {x_1}+....+\frac{1}{x_{k+1}}\right)=$

$\left(x_1+.....+x_k\right)\left(\frac{1}{x_1}+.... +\frac{1}{x_k}\right)+\frac{x_{k+1}}{x_{k+1}}+\lef t(x_1+....+x_k}\right)\left(\frac{1}{x_{k+1}}\righ t)+x_{k+1}\left(\frac{1}{x_1}+....+\frac{1}{x_k}\r ight)$

Whether or not P(k) being valid causes P(k+1) to be valid should now be clear.

Finally test for $n=1.$

**Archie Meade** · November 3rd 2010, 03:17 PM

No.4 was a bit more challenging.

Writing it in the way we normally use "k",

P(k)

$\displaystyle\sqrt{\sum_{i=1}^k\left(x_i-y_i\right)^2}\;\; \le\ \sqrt{\sum_{i=1}^k\left(x_i\right)^2}+\sqrt{\sum_{ i=1}^k\left(y_i\right)^2}$

P(k+1)

$\displaystyle\sqrt{\sum_{i=1}^{k+1}\left(x_i-y_i\right)^2}\;\; \le\ \sqrt{\sum_{i=1}^{k+1}\left(x_i\right)^2}+\sqrt{\s um_{i=1}^{k+1}\left(y_i\right)^2}$

We want to show that if P(k) is valid, then it will cause P(k+1) to be valid also.
Hence we try to write P(k+1) so that it contains the P(k) expression.
Then we can draw the conclusion.

Proof

$\displaystyle\sqrt{\sum_{i=1}^{k+1}\left(x_i-y_i\right)^2}\;\; \le\ \sqrt{\sum_{i=1}^{k+1}\left(x_i\right)^2}+\sqrt{\s um_{i=1}^{k+1}\left(y_i\right)^2}\;\;?$

Rewriting P(k+1)..

$\displaystyle\sqrt{\sum_{i=1}^k\left(x_i-y_i\right)^2+\left(x_{k+1}-y_{k+1}\right)^2}\;\; \le\ \sqrt{\sum_{i=1}^k\left(x_i\right)^2+\left(x_{k+1} \right)^2}+\sqrt{\sum_{i=1}^k\left(y_i\right)^2+\l eft(y_{k+1}\right)^2}\;\;?$

Squaring both sides,

$\displaystyle\sum_{i=1}^k\left(x_i-y_i\right)^2+\left(x_{k+1}-y_{k+1}\right)^2\;\;\le$

$\displaystyle\sum_{i=1}^k\left(x_i\right)^2+\left( x_{k+1}\right)^2+\sum_{i=1}^k\left(y_i\right)^2+\l eft(y_{k+1}\right)^2+2\sqrt{\sum_{i=1}^k\left(x_i\ right)^2+\left(x_{k+1}\right)^2}\sqrt{\sum_{i=1}^k \left(y_i\right)^2+\left(y_{k+1}\right)^2}\;?$

Subtracting $\left(x_{k+1}-y_{k+1}\right)^2=\left(x_{k+1}\right)^2+\left(y_{k +1}\right)^2-2\left(x_{k+1}\right)\left(y_{k+1}\right)$ from both sides,

$\displaystyle\sum_{i=1}^k\left(x_i-y_i\right)^2\;\;\le\ \sum_{i=1}^k\left(x_i\right)^2+\sum_{i=1}^k\left(y _i\right)^2+\left(x_{k+1}\right)^2-\left(x_{k+1}\right)^2+\left(y_{k+1}\right)^2-\left(y_{k+1}\right)^2+$

$\displaystyle\ +2\left(x_{k+1}\right)\left(y_{k+1}\right)+2\sqrt{ \sum_{i=1}^k\left(x_i\right)^2+\left(x_{k+1}\right )^2}\sqrt{\sum_{i=1}^k\left(y_i\right)^2+\left(y_{ k+1}\right)^2}\;\;?$

Hence, our rewritten P(k+1) is

$\displaystyle\sum_{i=1}^k\left(x_i-y_i\right)^2\;\;\le\ \sum_{i=1}^k\left(x_i\right)^2+\sum_{i=1}^k\left(y _i\right)^2+2\left(x_{k+1}\right)\left(y_{k+1}\rig ht)+$

$\displaystyle\ +2\sqrt{\sum_{i=1}^k\left(x_i\right)^2+\left(x_{k+ 1}\right)^2}\sqrt{\sum_{i=1}^k\left(y_i\right)^2+\ left(y_{k+1}\right)^2}\;\;?$

Rewriting P(k) by squaring both sides, to examine P(k+1)...

$\displaystyle\sum_{i=1}^k\left(x_i-y_i\right)^2\;\;\le\ \sum_{i=1}^k\left(x_i\right)^2+\sum_{i=1}^k\left(y _i\right)^2+2\sqrt{\sum_{i=1}^k\left(x_i\right)^2} \sqrt{\sum_{i=1}^k\left(y_i\right)^2}$

Examining the above rewritten P(k+1) and P(k) propositions,
it's easy to see that the RHS of the P(k+1) expression is greater than the RHS of the P(k) expression,
while the LHS is the same for both.

Therefore, if P(k) is valid, P(k+1) will as a result, also be valid.

Hence you only need to test for $n=1$ or $k=1.$

Thread: Four mathematical induction problems

LinkBack

Thread Tools

Display

Four mathematical induction problems

Similar Math Help Forum Discussions

mathematical induction

Rigorously prove the principle of complete induction from mathematical induction??

Mathematical Induction

Mathematical Induction help

Mathematical induction problems

Search Tags