
Linear Algebra Linear Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
September 15th, 2016, 05: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^{k1}}+...+n^{1/2}+n)$ And I have no idea how to find the pattern of that so I'm hoping I'm wrong. 
September 15th, 2016, 05:49 PM  #2 
Global Moderator Joined: Oct 2008 From: London, Ontario, Canada  The Forest City Posts: 7,958 Thanks: 1146 Math Focus: Elementary mathematics and beyond 
What recurrence relation?! You've given an expression in $n$. Why did you post this in Linear Algebra?

September 15th, 2016, 06: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.

September 15th, 2016, 06: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$ 
September 15th, 2016, 06:38 PM  #5 
Global Moderator Joined: Oct 2008 From: London, Ontario, Canada  The Forest City Posts: 7,958 Thanks: 1146 Math Focus: Elementary mathematics and beyond 
Um...shouldn't the $n$ have a subscript?

September 15th, 2016, 06:58 PM  #7 
Global Moderator Joined: Oct 2008 From: London, Ontario, Canada  The Forest City Posts: 7,958 Thanks: 1146 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$$ ? 
September 15th, 2016, 07:04 PM  #8 
Newbie Joined: Sep 2016 From: CO Posts: 6 Thanks: 0 
Yes, sorry I'm not good at Latex yet.

September 16th, 2016, 02:03 PM  #9 
Global Moderator Joined: Oct 2008 From: London, Ontario, Canada  The Forest City Posts: 7,958 Thanks: 1146 Math Focus: Elementary mathematics and beyond 
From WA: $$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. 
September 16th, 2016, 02:35 PM  #10 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,675 Thanks: 2655 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.


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 04:51 AM 
Recurrence Relation and Closed Form Relation  uniquegel  Algebra  4  September 8th, 2014 04:18 PM 
Recurrence relation  Dragonkiller  Linear Algebra  2  May 15th, 2012 10:49 AM 
recurrence relation fn+4  fe phi fo  Applied Math  3  December 4th, 2011 09:22 AM 
recurrence relation fn+4  fe phi fo  Real Analysis  1  December 31st, 1969 04:00 PM 