Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [recursion]

Recursion is the process of repeating items in a self-similar way. A recursive definition (or inductive definition) in mathematical logic and computer science is used to define an object in terms of itself. A recursive definition of a function defines values of a function for some inputs in terms of the values of the same function on other inputs. Please use the tag 'computability' instead for questions about "recursive functions" in computability theory

Recursion is the process of repeating items in a self-similar way. The most common application of recursion is in mathematics and computer science, in which it refers to a method of defining functions in which the function being defined is applied within its own definition.

Basically, a class of objects exhibiting recursive behaviour can be characterised by two features:

  • There must be a base criterion for which the function should not call itself.

  • Every other iteration of the function should move it closer to the base condition.

2829 questions
0
votes
1 answer

Solving a problem using the master theorem?

How can I solve this problem with master theorem. Giving asymptotic upper and lower bounds If $T(n)=4T(n/3)+ n log(n)$ a=4 b=3 k=1 for the formula $aT(n/b)+n^k log^b(n)$ if $a>b^k$ then $T(n)=\theta(n^{log_b^a})$ which is then does this mean the…
Fernando Martinez
  • 6,698
  • 19
  • 74
  • 108
0
votes
0 answers

Finding an explicit formula for An in terms of n.

Let $A_{1}= 5, A_{2} = 7,$ $A_{n+1} = A_{n} + 6A_{n-1}$. Find an explicit formula for $A_n$ in terms of $n$. Suppose $p_{n}$ is a sequence defined by $p_{1} = 0, p_{2} = 1$ & $\forall n$, $p_{n+1} = 2p_{n} - 2p_{n-1}$. Find a formula for…
user123
  • 83
0
votes
1 answer

How does one know T(a) is the base case in T(n) = T(n-a) + T(a) + cn

T(n) = T(n-a) + T(a) + cn Solve by drawing recursion tree. Typically when solving other recursion tree problems, I've calculated the height of the tree in terms of when the subproblems reach T(1). Why is it in this case that the height of the tree…
Sean Bollin
  • 229
0
votes
0 answers

Is this recursive?

I came across this formula in a neuroscience journal: $x = [sigma(y - z)] - w$ where: $z = a + \max(x)$ My question is, can you solve for $x$ if $x$ is a constituent of $z$?
y3trgfhsfgr
  • 101
0
votes
1 answer

Proofs related to counting the nodes of a recursive tree

Define Fibonacci numbers by $\text {Fib(n)} = \begin{cases} 0 & \text{if $n = 0$} \\[2ex] 1 & \text{if $n = 1$} \\[2ex] \text {Fib(n - 1) + Fib(n - 2)} & \text {otherwise} \end{cases}$ My textbook goes on to say: In fact, it is not hard to show…
Trees
  • 1
0
votes
2 answers

Solving this recursion question

Text-only For the sequence $10,50,250,1250,\ldots$ Determine the first form $a$ and the common ratio $r$. Infer an explicit formula for this sequence. Write its recursive form. Please check, if answer is correct? If wrong, please show correct…
user2534252
  • 45
-1
votes
1 answer

show the recursive sequence equation holds

Let a, b ∈ R. The sequence (an)n∈N is recursively defined as follows: a) Show that for all k ∈ N the equation holds b) Show that the sequence (an)n∈N converges and determine its limit. Hello everyone, First of all this is the whole question. I…
A O
  • 51
-1
votes
2 answers

Solutions of recursive equations using generating functions

Can someone explain me how solve exercise like this? Find solutions of recursive equations using generating functions: $$ a_n = a_{n-1} + 2n - 1\\ a_0= 0\\ n\ge 1 $$
KanekiSenpai
  • 29
-1
votes
1 answer

How to add function to a recursive equation?

If I have the equations $f(x)=30c^x$ and $g(x)=g(x-1)+f(x)$, $g(0)=30$ why is $g(x)=30xc^x+30$ not the answer when something like $h(x)=h(x-1)+c$, $h(t)=d$ would make $h(x)=c(x-t)+d$? What I try to do goes as follows $30c^x(x-0)+30$ or $30xc^x+30$…
Doshorte Dovencio
  • 101
-1
votes
3 answers

Recursion $f(n) = 3f(n-1) - 4f(n-3)$ with $f(0) = 1$ , $f(1) = -3$ , $f(2) = 2$

How can one solve the recursion $$f(n) = 3f(n-1) - 4f(n-3)$$ The start values are $f(0) = 1$ $f(1) = -3$ $f(2) = 2$ I tried to find a general pattern to prove it with induction, but I can't find one...
user608796
-1
votes
3 answers

Calculate Tithe from Income

Hi I need help calculating the amount I need to donate as tithe (1/10 of income) every year. Say my annual income before tax is $50000 and the tax rate is 30%. Which means my income after tax is $50000 x 0.7 = $35000. So I will donate $3500 as…
user1589188
  • 111
-1
votes
2 answers

Closed-form representation of the following recursively defined sequence

Trying to find a closed-form representation of the following recursively defined sequence: $a_{0}=1, a_{1}=2, a_{n+2}= a_{n+1} +2a_{n}$. Afraid that I am a little out of my depth here, i know i can use induction to prove but i don't know where to…
Pixe1
  • 13
-2
votes
1 answer

Proof by induction help

I don't know the full process of induction, as it's one of the harder questions on my upcoming test papers I thought i'd attempt to get a basic understanding; in order to get a 1/2 marks out of the question. However, since doing it I believe with a…
user118964
  • 11
-2
votes
1 answer

Solve the recursion

I am trying to solve the recursion $T (k) = T (k/5) + k^2$ and I can't figure out after the following step. $$\begin{align}T(k) &= T (k/5) + k^2\\ &= (T(k/25) + k^2/25) + k^2\\ &= (T(k/625) + k^2/625) + k^2/25 + k^2\\ &= T(1) + … + k^2/625 +…
AMR
  • 1
-2
votes
1 answer

For any integer n >=1, let Fn be the number of aa-free strings of length n. Determine F1, F2, F3

Question: We consider strings of characters, where each character is an element of {a; b; c}. Such a string is called aa-free, if it does not contain two consecutive a's. For any integer n > = 1, let Fn be the number of aa-free strings of length…
Toby
  • 373
1 2 3
…
12
13