Wikipedia:Reference desk/Archives/Mathematics/2018 April 29

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 29

Solving a recurrence

What's the solution of $T(n)=4T(n/3)+4T(2n/3)$? עברית (talk) 18:29, 29 April 2018 (UTC)

One solution is $T(n)=n^{3.612803505172812}$ --catslash (talk) 00:34, 30 April 2018 (UTC)

More specifically, T(n) = kn^a is a solution where k is arbitrary and a is a root of the equation 3^a=4(1+2^a). Usually a recurrence is used to to define a function on integers, so this is more of a functional equation. --RDBury (talk) 00:51, 30 April 2018 (UTC)

More generally, since the equation is first degree homogeneous in T, it is satisfied by an arbitrary linear combination of $n^{3.612803505172812}$ and any other independent solution. --catslash (talk) 01:26, 30 April 2018 (UTC)

There are an infinite number of complex solutions for the exponent, but obviously the set of all these solutions won't form a complete set as an arbitrary $T(n)$ does not satisfy the recurrence. Count Iblis (talk) 06:36, 30 April 2018 (UTC)

Thank you very much! עברית (talk) 18:54, 1 May 2018 (UTC)