My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum


Thanks Tree6Thanks
  • 2 Post By skipjack
  • 2 Post By mathman
  • 2 Post By skipjack
Reply
 
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.
babaliaris is offline  
 
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$.
Thanks from topsquark and babaliaris
skipjack is offline  
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)$.
Thanks from topsquark and babaliaris

Last edited by skipjack; March 7th, 2019 at 12:19 AM.
mathman is offline  
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?
babaliaris is offline  
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$.
Thanks from topsquark and babaliaris
skipjack is offline  
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$.
mathman is offline  
March 9th, 2019, 05:08 AM   #7
Senior Member
 
Joined: Oct 2015
From: Greece

Posts: 115
Thanks: 8

Quote:
Originally Posted by mathman View Post
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.
babaliaris is offline  
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.
mathman is offline  
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.
skipjack is offline  
Reply

  My Math Forum > High School Math Forum > Algebra

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 Pre-Calculus 1 November 28th, 2014 04:43 PM
mathematical induction,why not?! mashaheer Applied Math 1 May 27th, 2012 07:45 AM





Copyright © 2019 My Math Forum. All rights reserved.