 My Math Forum > Math Mathematical Induction Recursive Function Help!
 User Name Remember Me? Password

 Math General Math Forum - For general math related discussion and news

 March 6th, 2019, 04:56 AM #1 Senior Member   Joined: Oct 2015 From: Greece Posts: 107 Thanks: 6 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 10:46 AM. March 6th, 2019, 12:45 PM #2 Global Moderator   Joined: Dec 2006 Posts: 20,373 Thanks: 2010 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, 02:00 PM #3 Global Moderator   Joined: May 2007 Posts: 6,704 Thanks: 670 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 12:19 AM. March 6th, 2019, 02:27 PM #4 Senior Member   Joined: Oct 2015 From: Greece Posts: 107 Thanks: 6 Thank you so much! I approached it a little different but here is my result: Is it correct? March 8th, 2019, 08:34 AM #5 Global Moderator   Joined: Dec 2006 Posts: 20,373 Thanks: 2010 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, 01:33 PM #6 Global Moderator   Joined: May 2007 Posts: 6,704 Thanks: 670 Comment: Using $n=2^k$ seems unnecessary, when the induction can be done directly with $n\to 2n$. March 9th, 2019, 05:08 AM   #7
Senior Member

Joined: Oct 2015
From: Greece

Posts: 107
Thanks: 6

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 10:19 AM. March 9th, 2019, 12:33 PM #8 Global Moderator   Joined: May 2007 Posts: 6,704 Thanks: 670 I did not use $n=2^k$. The main point is that $1+log_2(n)=log_2(2n)$. 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 07:25 PM Antoniomathgini Algebra 3 July 25th, 2017 05:22 AM prismo69 Applied Math 2 March 14th, 2015 08:52 PM spuncerj Pre-Calculus 1 November 28th, 2014 04:43 PM mashaheer Applied Math 1 May 27th, 2012 07:45 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top       