My Math Forum Mathematical Induction Recursive Function Help!

 Algebra Pre-Algebra and Basic Algebra Math Forum

 March 6th, 2019, 04:56 AM #1 Senior Member   Joined: Oct 2015 From: Greece Posts: 137 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,968 Thanks: 2217 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,822 Thanks: 723 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: 137 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,968 Thanks: 2217 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,822 Thanks: 723 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: 137
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 10:19 AM.

 March 9th, 2019, 12:33 PM #8 Global Moderator   Joined: May 2007 Posts: 6,822 Thanks: 723 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,968 Thanks: 2217 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.

 Thread Tools Display Modes Linear 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