All Questions
Tagged with recursive-algorithms closed-form
22
questions
-4
votes
1
answer
129
views
Solving the recurrence $T(1) = 1$, $T(n) = T(n-1) + n^2$ [duplicate]
How do you solve the following recurrence?
$T(1) = 1$
$T(n) = T(n-1) + n^2$
1
vote
1
answer
558
views
How to convert recursive function into explicit form
I have the recursive expression:
$$f(n) = 1 + f\left(\left\lceil {\frac{2n - 1}{6}} \right\rceil\right)\text{ for }n>1$$
and
$$f(0) = 0$$
$$f(1) = 0$$
And I'm trying to turn it into its explicit / ...
- 21
1
vote
1
answer
655
views
Closed-form expression for a recursive formula
I'm trying to calculate the closed-form expression of the recursive
$a_n = \frac{a_{n-1} + a_{n-2}}{3}$
Where $a_0 = 0, $ $a_1 = \frac {1}{3}$, and $a_2 = \frac {1}{9}$
I have tried to mimic the ...
- 31
0
votes
0
answers
32
views
How to express $n$ unknown variables in a system with $n-1$ equations
I have a system of $n-1$ equations which have $n$ unknown variables, as follows:
\begin{align}
&\text{Equation $1$} &&x_1A_{1,1}+...+x_nA_{1,n}=0\\
& \hspace{1cm}\vdots && \...
- 89
2
votes
2
answers
83
views
Converting Circular formulae to Independent functions
I have a set of equations which I'm trying to transform from a recursive relationship to a more absolute/relative notation. Ideally this is to transform row-based logic into a set-based one for SQL.
I ...
- 75
0
votes
1
answer
326
views
(Calculus) Solving a geometric series word problem
I’m struggling with understanding how to solve part B of the following problem:
Consider an outdoor pool initially filled with 20,000 gallons of water. Each day, 4% of the water in the pool ...
- 11
0
votes
0
answers
29
views
How to prove that a recursive function with inner summation is approximately equal to some closed-form equation?
The following problem is taken from an algorithms textbook(specifically, in the context of complexity analysis of recursive algorithms.)
Starting from the equation:
$$nf(n) = n(n-1) + 2 \sum_{k=1}...
- 111
1
vote
1
answer
269
views
Does this recursive function have a closed-form solution?
Consider the following recursive function:
$$
z(i) = \begin{cases}
z(i + 8) + 1 & i < 0 \\
z(i - 7) & i > 2 \\
0 & 0 \leq i \leq 2
\end{cases}
$$
Does this recursive function have ...
- 486
0
votes
1
answer
63
views
Is there a rule behind why $\left \{ 1+(-1/2)^n) \right \}^{+\infty}_{n=1}$ is $a_{n+2}=1/2(a_{n+1}+a_{n}) , a_{0} = 2 , a_{1}=1/2$ in recursive form?
I understand that both expresions represent the same sequence of numbers. It starts at $a_{0}=2$ and oscilate around 1 converging to it from up and down.
I have been playing around with the explicit ...
0
votes
0
answers
62
views
Stuck Simplifying for a Fibonacci Series
I am attempting to solve for $n$ in the equation:
$g_n=g_1F_{n-1}+g_2F_n$
where $F_n$ is the $n$th Fibonacci number. I know that $g_0$ and $g_1$ will be positive integers such that $0 < g_1 \leq ...
- 149
1
vote
1
answer
40
views
How would I go about converting this recurrence relation to closed form?
So I looked at a part of code and came up with a recurrence relation for it and I got:
$$T(0) = 1,$$
$$T(n) = 3 + 2T(n-1).$$
Then I solved it using substitution and got:
$$T(n) = 2^i*T(n-i)+3(2^i-1)....
- 23
0
votes
0
answers
371
views
Convert any Recursive Summation into an Integral
My goal is to solve a recursive summation without iteration (a lot to ask for I know).
Is there a technique for converting a recursive summation into an integral?
For example, these two recursive ...
- 81
1
vote
0
answers
440
views
Binary Recursive GCD algorithm analysis
This is a pseudocode for a Binary GCD algorithm:
...
0
votes
1
answer
77
views
Linear Search Recursive Runtime
Assume this is the pseudocode of a Linear Search:
...
0
votes
2
answers
247
views
Closed form for recurrence relation $T(n) = T(\dfrac{n}{3}) + T(\dfrac{2n}{3}) + \mathcal{O}(n)$
I am familiar with the Master's theorem and with the idea of telescoping a recurrence relation to find a closed form, but I could not solve this one:
$$T(n) = T(\dfrac{n}{3}) + T(\dfrac{2n}{3}) + \...
- 543