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 :

{(2 k + 1)}^{n} \in O \forall k, n \in Z

Answered by Rasheed Soomro last updated on 12/Oct/16

{(2 k + 1)}^{n} = (\begin{matrix} n \\ 0 \end{matrix}) {(2 k)}^{n} + (\begin{matrix} n \\ 1 \end{matrix}) {(2 k)}^{n - 1} + \dots + (\begin{matrix} n \\ r \end{matrix}) {(2 k)}^{n - r}

+ \dots . + (\begin{matrix} n \\ n - 1 \end{matrix}) (2 k) + 1

= (2 k) ((\begin{matrix} n \\ 0 \end{matrix}) {(2 k)}^{n - 1} + (\begin{matrix} n \\ 1 \end{matrix}) {(2 k)}^{n - 2} + \dots + (\begin{matrix} n \\ r \end{matrix}) {(2 k)}^{n - r - 1}

+ \dots . + (\begin{matrix} n \\ n - 1 \end{matrix})) + 1

= 2 km + 1 \in O

Hence {(2 k + 1)}^{n} \in O

Proved .

Commented by FilupSmith last updated on 12/Oct/16

Thanks . I was certain this was how to

solve this problem!