My Math Forum Finding the Closed-Form Expression For a Recurrence

 Applied Math Applied Math Forum

 October 11th, 2013, 06:10 PM #1 Senior Member   Joined: Jan 2012 Posts: 159 Thanks: 0 Finding the Closed-Form Expression For a Recurrence n is deemed to only be a power of 3. $f(n) = \begin{cases} 4, & \text{ if } n = 1 \\ f(\lfloor \frac{n}{3} \rfloor) + n^2 - 3, & \text{ if } n > 1 \end{cases}$ Doing repeated substitution I get: $f(\lfloor \frac{n}{3^2} \rfloor) + (\frac{n}{3})^2 +n^2 - 3 -3 f(\lfloor \frac{n}{3^3} \rfloor) + (\frac{n}{3^2})^2+ (\frac{n}{3})^2 +n^2 - 3 -3 -3$ So this is going to keep going until $3^i$ becomes equal to whatever n is. Also since n is a power of 3 we know this will be when $n= 3^i$ Therefore $f(\lfloor \frac{3^i}{3^i} \rfloor) + (\frac{3^i}{3^{i-1}})^2+(\frac{3^i}{3^{i-2}})^2 +\ldots + (\frac{3^i}{3^1})^2 +(\frac{3^i}{3^0})^2 - 3i$ Not really sure where to go from here as it seems to be a geometric series yet that really does not help me with the closed form. Also I have tried to just work out a pattern looking at the numbers: $f(1) = 4 f(3) = f(\lfloor \frac{3}{3} \rfloor) + 3^2 - 3 = f(1) + 3^2 - 3 = 4 + 3^2 -3 = 10 f(9) = f(\lfloor \frac{9}{3} \rfloor) + 9^2 - 3 = f(3) + 3^4 - 3 = 4 + 3^2 + 3^4 -3 -3 = 88 f(27) = f(\lfloor \frac{27}{3} \rfloor) + 27^2 - 3 = f(9) + 3^6 -3 = 4 + 3^2 + 3^4 +3^6 -3 -3 -3$ so the 4 and the -3i I get but not to sure how to resolve the rest. I believe it has to do with finding closed form for a geometric series... Any help would be appreciated!

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Davebungo Calculus 0 January 13th, 2014 02:30 PM gelatine1 Algebra 3 September 1st, 2013 10:57 PM kriegor Applied Math 1 March 22nd, 2013 04:48 PM joatmon Real Analysis 2 January 24th, 2012 08:33 PM ChessTal Linear Algebra 5 July 4th, 2011 07:03 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top