# Thread: Four mathematical induction problems

1. ## Four mathematical induction problems

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

Thank you so much!!!

2. 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 \displaystyle\ 1+\frac{1}{\sqrt{2}}+....+\frac{1}{\sqrt{k}}>\sqrt {k}$

P(k+1)

$\displaystyle \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 \displaystyle\ 1+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{k}}+\frac{ 1}{\sqrt{k+1}}>\sqrt{k}+\frac{1}{\sqrt{k+1}}$

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

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

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

then

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

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

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

3. Originally Posted by Archie Meade
For 1.

P(k)

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

P(k+1)

$\displaystyle \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 \displaystyle\ 1+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{k}}+\frac{ 1}{\sqrt{k+1}}>\sqrt{k}+\frac{1}{\sqrt{k+1}}$

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

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

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

then

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

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

hence, you need to examine the case for $\displaystyle n=2.$
Thank you very much!

4. For 2.

$\displaystyle \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 $\displaystyle n$ or $\displaystyle k$

P(k)

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

for a nesting depth of k.

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

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

$\displaystyle \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 $\displaystyle k+1.$

P(k) will definately be valid if $\displaystyle \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 \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 $\displaystyle n=1$ or $\displaystyle k=1..$

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

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

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

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

5. No.3 is straightforward.

For $\displaystyle x_k>0,$ prove by induction that

$\displaystyle \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)

$\displaystyle \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)

$\displaystyle \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

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

$\displaystyle \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)=$

$\displaystyle \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)=$

$\displaystyle \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 $\displaystyle n=1.$

6. No.4 was a bit more challenging.

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

P(k)

$\displaystyle \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 \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 \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 \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 \displaystyle\sum_{i=1}^k\left(x_i-y_i\right)^2+\left(x_{k+1}-y_{k+1}\right)^2\;\;\le$

$\displaystyle \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 $\displaystyle \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 \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 \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 \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 \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 \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 $\displaystyle n=1$ or $\displaystyle k=1.$