
Algebra PreAlgebra and Basic Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
March 6th, 2019, 04:56 AM  #1 
Senior Member Joined: Oct 2015 From: Greece Posts: 115 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 10:46 AM. 
March 6th, 2019, 12:45 PM  #2 
Global Moderator Joined: Dec 2006 Posts: 20,484 Thanks: 2041 
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$. 
March 6th, 2019, 02:00 PM  #3 
Global Moderator Joined: May 2007 Posts: 6,732 Thanks: 689 
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)$.
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: 115 Thanks: 8 
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,484 Thanks: 2041 
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$. 
March 8th, 2019, 01:33 PM  #6 
Global Moderator Joined: May 2007 Posts: 6,732 Thanks: 689 
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: 115 Thanks: 8  Quote:
$\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,732 Thanks: 689 
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 09:31 PM. 
March 23rd, 2019, 09:41 PM  #9 
Global Moderator Joined: Dec 2006 Posts: 20,484 Thanks: 2041 
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  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Recursive definition and induction  CStudent  Elementary Math  3  December 2nd, 2018 07:25 PM 
Mathematical Induction  Antoniomathgini  Algebra  3  July 25th, 2017 05:22 AM 
Mathematical Induction (Prove function is always divisible by 36)  prismo69  Applied Math  2  March 14th, 2015 08:52 PM 
Mathematical Induction.  spuncerj  PreCalculus  1  November 28th, 2014 04:43 PM 
mathematical induction,why not?!  mashaheer  Applied Math  1  May 27th, 2012 07:45 AM 