My Math Forum  

Go Back   My Math Forum > College Math Forum > Linear Algebra

Linear Algebra Linear Algebra Math Forum


Reply
 
LinkBack Thread Tools Display Modes
September 15th, 2016, 06:24 PM   #1
Newbie
 
Joined: Sep 2016
From: CO

Posts: 6
Thanks: 0

Solve this recurrence relation with repeated subsitution

$\displaystyle \sqrt(n)T(\sqrt(n)+n$
I've tried what I think is right, but I came up with:
$\displaystyle (n^{1/2}*n^{1/2^{2}}*...*n^{1/2^{k}})T(n^{1/2^{k}})+(n^{1/2^{k-1}}+...+n^{1/2}+n)$
And I have no idea how to find the pattern of that so I'm hoping I'm wrong.
Hydro is offline  
 
September 15th, 2016, 06:49 PM   #2
Global Moderator
 
greg1313's Avatar
 
Joined: Oct 2008
From: London, Ontario, Canada - The Forest City

Posts: 7,912
Thanks: 1110

Math Focus: Elementary mathematics and beyond
What recurrence relation?! You've given an expression in $n$. Why did you post this in Linear Algebra?
greg1313 is offline  
September 15th, 2016, 07:27 PM   #3
Newbie
 
Joined: Sep 2016
From: CO

Posts: 6
Thanks: 0

This is for my Analysis of Algorithms class. I'm not sure where else to put it so I was hoping Linear was related.
Hydro is offline  
September 15th, 2016, 07:28 PM   #4
Newbie
 
Joined: Sep 2016
From: CO

Posts: 6
Thanks: 0

As for the format, does this change anything?
$\displaystyle T(n) = \sqrt(n)T\sqrt(n)+n$ for $\displaystyle n\leq 2$
Hydro is offline  
September 15th, 2016, 07:38 PM   #5
Global Moderator
 
greg1313's Avatar
 
Joined: Oct 2008
From: London, Ontario, Canada - The Forest City

Posts: 7,912
Thanks: 1110

Math Focus: Elementary mathematics and beyond
Um...shouldn't the $n$ have a subscript?
greg1313 is offline  
September 15th, 2016, 07:49 PM   #6
Newbie
 
Joined: Sep 2016
From: CO

Posts: 6
Thanks: 0

no
It is solved in the first method presented here. I understand this simple example, but idk about the one I posted.
Hydro is offline  
September 15th, 2016, 07:58 PM   #7
Global Moderator
 
greg1313's Avatar
 
Joined: Oct 2008
From: London, Ontario, Canada - The Forest City

Posts: 7,912
Thanks: 1110

Math Focus: Elementary mathematics and beyond
The system caught your link. I've approved the post.

Just to be sure we're on the same page, do you intend

$$T(n)=\sqrt nT(\sqrt n)+n$$

?
greg1313 is offline  
September 15th, 2016, 08:04 PM   #8
Newbie
 
Joined: Sep 2016
From: CO

Posts: 6
Thanks: 0

Yes, sorry I'm not good at Latex yet.
Hydro is offline  
September 16th, 2016, 03:03 PM   #9
Global Moderator
 
greg1313's Avatar
 
Joined: Oct 2008
From: London, Ontario, Canada - The Forest City

Posts: 7,912
Thanks: 1110

Math Focus: Elementary mathematics and beyond
From W|A:

$$T(n)=\frac{n}{e^2}+\frac{n\log(\log(n))}{\log(2) }$$

I've verified it with a CAS and I don't know how to compute it. It seems like a somewhat (at least) difficult problem.
greg1313 is offline  
September 16th, 2016, 03:35 PM   #10
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,599
Thanks: 2587

Math Focus: Mainly analysis and algebra
The OP's relation is invalid for n=1. It also fails to define T for most values of n as far as I can see.
v8archie is offline  
Reply

  My Math Forum > College Math Forum > Linear Algebra

Tags
recurrence, relation, repeated, solve, subsitution



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Solve this Recurrence Relation? CSteiner Real Analysis 8 January 5th, 2016 05:51 AM
Recurrence Relation and Closed Form Relation uniquegel Algebra 4 September 8th, 2014 05:18 PM
Recurrence relation Dragonkiller Linear Algebra 2 May 15th, 2012 11:49 AM
recurrence relation fn+4 fe phi fo Applied Math 3 December 4th, 2011 10:22 AM
recurrence relation fn+4 fe phi fo Real Analysis 1 December 31st, 1969 04:00 PM





Copyright © 2019 My Math Forum. All rights reserved.