Menu Close

Prove-or-disprove-that-2k-1-n-O-k-n-Z-




Question Number 8468 by FilupSmith last updated on 12/Oct/16
Prove or disprove that:  (2k+1)^n ∈O      ∀k,n∈Z
$$\mathrm{Prove}\:\mathrm{or}\:\mathrm{disprove}\:\mathrm{that}: \\ $$$$\left(\mathrm{2}{k}+\mathrm{1}\right)^{{n}} \in\mathbb{O}\:\:\:\:\:\:\forall{k},{n}\in\mathbb{Z} \\ $$
Answered by Rasheed Soomro last updated on 12/Oct/16
(2k+1)^n = ((n),(0) )(2k)^n + ((n),(1) )(2k)^(n−1) +...+ ((n),(r) )(2k)^(n−r)                       + ....+ (((    n)),((n−1)) )(2k)+1                  =(2k)( ((n),(0) )(2k)^(n−1) + ((n),(1) )(2k)^(n−2) +...+ ((n),(r) )(2k)^(n−r−1)                       + ....+ (((    n)),((n−1)) ) )+1                     =2km+1∈O  Hence (2k+1)^n ∈O  Proved.
$$\left(\mathrm{2k}+\mathrm{1}\right)^{\mathrm{n}} =\begin{pmatrix}{\mathrm{n}}\\{\mathrm{0}}\end{pmatrix}\left(\mathrm{2k}\right)^{\mathrm{n}} +\begin{pmatrix}{\mathrm{n}}\\{\mathrm{1}}\end{pmatrix}\left(\mathrm{2k}\right)^{\mathrm{n}−\mathrm{1}} +…+\begin{pmatrix}{\mathrm{n}}\\{\mathrm{r}}\end{pmatrix}\left(\mathrm{2k}\right)^{\mathrm{n}−\mathrm{r}} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:+\:….+\begin{pmatrix}{\:\:\:\:\mathrm{n}}\\{\mathrm{n}−\mathrm{1}}\end{pmatrix}\left(\mathrm{2k}\right)+\mathrm{1} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:=\left(\mathrm{2k}\right)\left(\begin{pmatrix}{\mathrm{n}}\\{\mathrm{0}}\end{pmatrix}\left(\mathrm{2k}\right)^{\mathrm{n}−\mathrm{1}} +\begin{pmatrix}{\mathrm{n}}\\{\mathrm{1}}\end{pmatrix}\left(\mathrm{2k}\right)^{\mathrm{n}−\mathrm{2}} +…+\begin{pmatrix}{\mathrm{n}}\\{\mathrm{r}}\end{pmatrix}\left(\mathrm{2k}\right)^{\mathrm{n}−\mathrm{r}−\mathrm{1}} \right. \\ $$$$\left.\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:+\:….+\begin{pmatrix}{\:\:\:\:\mathrm{n}}\\{\mathrm{n}−\mathrm{1}}\end{pmatrix}\:\right)+\mathrm{1} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:=\mathrm{2km}+\mathrm{1}\in\mathbb{O} \\ $$$$\mathrm{Hence}\:\left(\mathrm{2k}+\mathrm{1}\right)^{\mathrm{n}} \in\mathbb{O} \\ $$$$\mathrm{Proved}. \\ $$$$ \\ $$
Commented by FilupSmith last updated on 12/Oct/16
Thanks. I was certain this was how to  solve this problem!
$$\mathrm{Thanks}.\:\mathrm{I}\:\mathrm{was}\:\mathrm{certain}\:\mathrm{this}\:\mathrm{was}\:\mathrm{how}\:\mathrm{to} \\ $$$$\mathrm{solve}\:\mathrm{this}\:\mathrm{problem}! \\ $$

Leave a Reply

Your email address will not be published. Required fields are marked *