 My Math Forum Mathematical Induction Recursive Function Help!

 Algebra Pre-Algebra and Basic Algebra Math Forum

 March 6th, 2019, 05:56 AM #1 Senior Member   Joined: Oct 2015 From: Greece Posts: 139 Thanks: 8 Mathematical Induction Recursive Function Help! $\displaystyle T(n) = \begin{cases} 2, \quad n=2 \\ 2T(n/2) + n, \quad n=2^k \quad k>1 \end{cases}$ Prove (If n is a power of 2) using mathematical induction that: $\displaystyle T(n) = n\log_2(n)$ I tried it but I can't solve it, probably because I don't know how to use the information that n is a power of two. This is where I'm stuck: 1) For n=2: $\displaystyle T(2) = 2\log_2(2) \Leftrightarrow 2 = 2$ 2) Let's assume that for n=t the solution is being satisfied: $\displaystyle T(t) = 2T(t/2) + t = t\log_2(t)$ 3) Then, for n = t+1: $\displaystyle T(t+1) = 2T(\frac{t+1}{2}) + t+1 = (t+1)\log_2(t+1)$ I can't find a way to make the equation 2 appear so I can use it in 3 Thanks. Last edited by skipjack; March 6th, 2019 at 11:46 AM. March 6th, 2019, 01:45 PM #2 Global Moderator   Joined: Dec 2006 Posts: 21,124 Thanks: 2332 Let $n = 2^k$, where $k$ is any natural number, so that $2n = 2\left(2^k\right) = 2^{k+1}$, and define $S(k) = T\left(2^k\right)$. Writing $S(k)$ for $T\left(2^k\right)$, $S(1) = 2$. Assuming $S(k)= k \cdot 2^k$ for some value of $k$ (which is true for $k = 1$), $S(k + 1) = 2S(k) + 2\left(2^k\right) = 2k \cdot 2^k + 2\left(2^k\right) = 2(k + 1)2^k = (k + 1)2^{k+1}$. By induction, $S(k)= k \cdot 2^k$ holds for all $k$. In the original notation, that becomes $T(n) \equiv n\log_2n$. Thanks from topsquark and babaliaris March 6th, 2019, 03:00 PM #3 Global Moderator   Joined: May 2007 Posts: 6,855 Thanks: 744 The induction step is from $n$ to $2n$. $T(2n)=2T(n)+2n=2n\log_2(n)+2n=2n(1+\log_2(n))$. Using $\log_2(2)=1$, we get $T(2n)=2n\log_2(2n)$. Thanks from topsquark and babaliaris Last edited by skipjack; March 7th, 2019 at 01:19 AM. March 6th, 2019, 03:27 PM #4 Senior Member   Joined: Oct 2015 From: Greece Posts: 139 Thanks: 8 Thank you so much! I approached it a little different but here is my result: Is it correct? March 8th, 2019, 09:34 AM #5 Global Moderator   Joined: Dec 2006 Posts: 21,124 Thanks: 2332 It's correct, but I recommend using a formal style for a proof by induction. For example: Let $P(n)$ be the proposition that $T(n) = n\log_2(n)$, where $n = 2^k$ and $k$ is any positive integer, i.e. (in terms of $k$ alone) that $T\left(2^k\right) = 2^k\!\cdot\! k$, where $k$ is any positive integer. The base case, $T\left(2^1\right) = 2^1\!\cdot\!1$, is true because $T(2) = 2$ is given. Assume that $T\left(2^k\right) = 2^k\!\cdot\! k$ holds for some (arbitrary) positive integer, $k$. \displaystyle \begin{align*}T\left(2^{k+1}\right) &= 2T\left(2^{k+1}/2\right) + 2^{k+1} \text{ (given)} \\ &= 2T\left(2^k\right) + 2^{k+1} \\ &= 2\!\cdot\!2^k\!\cdot\! k + \!2^{k+1} \text{ (by the above assumption)} \\ &= 2^{k+1}\!\cdot\! k + \!2^{k+1} \\ & = 2^{k+1}\!\cdot\! (k + 1)\end{align*} i.e. $P\left(2^{k+1}\right)$ is true. By mathematical induction, $P(n)$, where $n=2^k$, is true for every positive integer value of $k$. Thanks from topsquark and babaliaris March 8th, 2019, 02:33 PM #6 Global Moderator   Joined: May 2007 Posts: 6,855 Thanks: 744 Comment: Using $n=2^k$ seems unnecessary, when the induction can be done directly with $n\to 2n$. March 9th, 2019, 06:08 AM   #7
Senior Member

Joined: Oct 2015
From: Greece

Posts: 139
Thanks: 8

Quote:
 Originally Posted by mathman Comment: Using $n=2^k$ seems unnecessary, when the induction can be done directly with $n\to 2n$.
You mean that in the assumption step I use:
$\displaystyle T(n) = n\log_2(n)$

And in the induction step: $\displaystyle T(2n) = 2n\log_2(2n)$ because
$\displaystyle n = 2^k \Leftrightarrow 2n = 2^{k+1}$

????

Nice ideas by the way; even though I'm a university student, I never solved induction problems in my math life. So I'm quite new to this.

Last edited by skipjack; March 9th, 2019 at 11:19 AM. March 9th, 2019, 01:33 PM #8 Global Moderator   Joined: May 2007 Posts: 6,855 Thanks: 744 I did not use $n=2^k$. The main point is that $1+\log_2(n)=\log_2(2n)$. Last edited by skipjack; March 23rd, 2019 at 10:31 PM. March 23rd, 2019, 10:41 PM #9 Global Moderator   Joined: Dec 2006 Posts: 21,124 Thanks: 2332 You can avoid using $k$ for most of the steps, but what you are proving is true only when $n$ is a positive integer power of 2. Tags function, induction, mathematical, recursive Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post CStudent Elementary Math 3 December 2nd, 2018 08:25 PM Antoniomathgini Algebra 3 July 25th, 2017 06:22 AM prismo69 Applied Math 2 March 14th, 2015 09:52 PM spuncerj Pre-Calculus 1 November 28th, 2014 05:43 PM mashaheer Applied Math 1 May 27th, 2012 08:45 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top      