319. Some problems with induction.

by Virgil Nicula, Sep 20, 2011, 6:33 AM

PP1. Suppose that for a given $p\in \mathbb N^*$ exists $s\in \mathbb N^*$ so that $s\ge 2^p-1$ and $2^s>s^p$ .

Then $(\forall )\ n\in \mathbb N^*\ ,\ n\ge s$ we have $2^n>n^p$ .


Proof. Indeed :

$\blacktriangleright$ $n=s\Rightarrow 2^s>s^p$ . So the given claim is true for $n:=s$.

$\blacktriangleright$ Suppose that for some $m\ge s>2^p-1$ , $2^m>m^p\ (*)$ . Then $2^{m+1}=$ $2\cdot 2^m>2\cdot m^p=$

$m^p+m\cdot m^{p-1}> $ $m^p+\left(2^p-1\right)\cdot m^{p-1}=$ $m^p+\left(\sum_{k=1}^pC_p^k\right)\cdot m^{p-1}>$ $m^p+\sum_{k=1}^pC_p^km^{p-k}=$

$\sum_{k=0}^pC_p^km^{p-k}=(m+1)^p$ . Now we proved that $2^n>n^p$ , $\forall\ n\in\mathbb N^*\ ,\ n> s$ .

Particular case. For $p=3$ exists $s=10\ge 2^3-1=7$ so that $2^{10}>10^3$ . Then $2^n>n^3$ for any $n\ge 10$ .



PP2. Let $ z_k \in\mathbb C$ with $ |z_k|=1 $ , where $k\in\overline{1,n}$ and $ E= \frac{(z_{1}+z_{2})(z_{2}+z_{3}) \cdots (z_{n-1}+z_{n})(z_{n}+z_{1})}{z_{1}.z_{2}\cdots z_{n}} $ . Prove that $ E\in\mathbb R$ .

Proof 1 (direct). $ z_k \in\mathbb C$ with $ |z_k|=1$ , where $k\in\overline{1,n}\iff$ $ z_k\cdot \overline z_k=1$ , where $k\in\overline{1,n}\iff$ .

Therefore, $\overline E=\frac {\left(\overline z_{1}+\overline z_{2}\right)\left(\overline z_{2}+\overline z_3\right) \cdots \left(\overline z_{n-1}+\overline z_{n}\right)\left(\overline z_{n}+\overline z_{1}\right)}{\overline z_1\cdot\overline z_2\cdots\overline z_{n-1}\cdot\overline z_n}\iff$

$\overline E=\frac {\left(\frac {1}{z_{1}}+\frac {1}{ z_{2}}\right)\left(\frac {1}{ z_{2}}+\frac  {1}{ z_3}\right) \cdots \left(\frac {1}{ z_{n-1}}+\frac {1}{ z_{n}}\right)\left(\frac {1}{ z_{n}}+\frac {1}{ z_{1}}\right)}{\frac {1}{z_1}\cdot\frac {1}{ z_2}\cdots\frac {1}{z_{n-1}}\cdot\frac {1}{z_n}}=E$ , i.e. $E=\overline E\iff E\in\mathbb R$ .

Proof 2 (induction). The cases where $n\in\overline{1,2}$ are obvious. Suppose that $E_n\in\mathbb R$ . Then $E_{n+1}=\frac{(z_{n}+z_{n+1})(z_1+z_{n+1})}{(z_{n}+z_1)z_{n+1}}\cdot E_{n}$.

Therefore, $E_{n+1}\in\mathbb R\iff$ $1+\frac{z_1z_{n}+z_{n+1}^{2}}{(z_1+z_{n})z_{n+1}}\in\mathbb R\iff$ $\frac{z_1z_{n}+z_{n+1}^{2}}{(z_1+z_{n})z_{n+1}}\in\mathbb R$ . By dividing numerator and demominator by $z_{n+1}^{2}$

and letting $u=\frac{z_1}{z_{n+1}}$ and $v=\frac{z_{n}}{z_{n+1}}$ this simplifies to proving that $\frac{uv+1}{u+v}\in\mathbb R$ , where $|u|=|v|=1$ . This can be shown by simple trig bashing.



PP3 (without complex numbers). Let $a\in\mathbb R$ and $x\in\mathbb C^*$ such that $x + \frac 1x = 2\cdot\cos a$ . Prove that for any $n\in\mathbb N$ we have $x^n+\frac {1}{x^n}=2\cdot\cos na$ .

Proof 1. Let $P(n)\ :\ x^n+\frac{1}{x^n}=2\cdot \cos na$ . We know that $P(1)$ is true. Let's prove $P(2)$. We have $ x^2+\frac{1}{x^2}=$ $\left(x+\frac{1}{x}\right)^2-2=$ $4\cos^2a-2=$ $2\cos 2a$ .

I"ll prove the implication $P(n-1)\ ,\ P(n)\Longrightarrow P(n+1)$. I"use the identity $a_1^{n+1}+a_2^{n+1}=$ $\left(a_1+a_2\right)\left(a_1^n+a_2^n\right)-$ $a_1a_2\left(a_1^{n-1}+a_2^{n-1}\right)\ ,$

$\forall a_1\ ,\ \forall a_2\in \mathbb{R}$ . Using this for $a_1:=x\ ,\ a_2:=\frac{1}{x}$ obtain that $x^{n+1}+\frac{1}{x^{n+1}}=$ $ \left(x+\frac{1}{x}\right)\left(x^n+\frac{1}{x^n}\right)-$ $\left(x^{n-1}+\frac{1}{x^{n-1}}\right)=$

$4\cos a \cos na-2\cos (n-1)a=$ $2\cdot\left[\cos (n-1)a+\cos (n+1)a\right]-2\cos (n-1)a=$ $2\cos  (n+1)a$ which proves the problem through induction.

Proof 2. $x+\frac 1x=2\cdot\cos a\iff$ $x^2-2x\cdot\cos a+1=0\iff$ $\left\{x,\frac 1x\right\}=\left\{\cos a\pm i\cdot\sin a\right\}\implies$ $x^n+\frac {1}{x^n}=2\cdot\cos na$ .
This post has been edited 11 times. Last edited by Virgil Nicula, Nov 20, 2015, 8:14 AM

Comment

0 Comments

Own problems or extensions/generalizations of some problems which was posted here.

avatar

Virgil Nicula
Archives
+ October 2017
+ September 2017
+ December 2016
+ October 2016
+ February 2016
+ September 2013
+ October 2010
+ September 2010
Shouts
Submit
  • orzzzzzzzzz

    by mathMagicOPS, Jan 9, 2025, 3:40 AM

  • this css is sus

    by ihatemath123, Aug 14, 2024, 1:53 AM

  • 391345 views moment

    by ryanbear, May 9, 2023, 6:10 AM

  • We need virgil nicula to return to aops, this blog is top 10 all time.

    by OlympusHero, Sep 14, 2022, 4:44 AM

  • :omighty: blog

    by tigerzhang, Aug 1, 2021, 12:02 AM

  • Amazing blog.

    by OlympusHero, May 13, 2021, 10:23 PM

  • the visits tho

    by GoogleNebula, Apr 14, 2021, 5:25 AM

  • Bro this blog is ripped

    by samrocksnature, Apr 14, 2021, 5:16 AM

  • Holy- Darn this is good. shame it's inactive now

    by the_mathmagician, Jan 17, 2021, 7:43 PM

  • godly blog. opopop

    by OlympusHero, Dec 30, 2020, 6:08 PM

  • long blog

    by MrMustache, Nov 11, 2020, 4:52 PM

  • 372554 views!

    by mrmath0720, Sep 28, 2020, 1:11 AM

  • wow... i am lost.

    369302 views!

    -piphi

    by piphi, Jun 10, 2020, 11:44 PM

  • That was a lot! But, really good solutions and format! Nice blog!!!! :)

    by CSPAL, May 27, 2020, 4:17 PM

  • impressive :D
    awesome. 358,000 visits?????

    by OlympusHero, May 14, 2020, 8:43 PM

72 shouts
Tags
About Owner
  • Posts: 7054
  • Joined: Jun 22, 2005
Blog Stats
  • Blog created: Apr 20, 2010
  • Total entries: 456
  • Total visits: 404398
  • Total comments: 37
Search Blog
a