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

Explicit formula of a difference equation

I have a difference equation I want to convert to a explicit formula and I'm currently stuck. The difference equation is as follows: $$ N_x = N_{x-1} + N_{x-3}, (f(x) = f(x-1) + f(x-3)), where: N_3 = 1, N_4 = 2, N_5 = 3 $$ I want to find the…
Reindier
  • 1
0
votes
2 answers

Need help understanding this recursion via pseudocode

Given the recursive algorithm in this pseudocode: RTC(n) Input: A nonnegative integer, n Output: A numerator or denominator (depending on parity of n) in an approximation of If n < 3 Return (n + 1) If n >= 3 t: = RTC(n – 1) If n is…
Academic Reboot
  • 13
0
votes
2 answers

Proving a recursion is less than two

The sequence $(a_n)$ is defined by $a_1 = \frac{1}{2}$ and $a_n = a_{n - 1}^2 + a_{n - 1}$ for $n \ge 2.$ Prove that $\frac{1}{a_1 + 1} + \frac{1}{a_2 + 1} + \dots + \frac{1}{a_n + 1} < 2$ for all $n \ge 1.$ So far, I have manipulated the given…
fds-mqdwqmqkdwl
  • 113
0
votes
4 answers

Solving recursive formula including a sum

I have the following formula $$T(1) = 1 $$ $$T(n) = \sum_{i=1}^{n-1}T(i) + n^2$$ And I have to find an iterative form of any $T(n)$ for $n>1$ One thing I have managed to accomplish so far is calculating $$T(n+1) = 2T(n) + 2n + 1$$ but I don't really…
Matjag
  • 1
0
votes
1 answer

Changing the index variable in a recursion relation

Can I change $$ x_{n+2} = 14x_{n+1} - 49x_n + n7^n\\ n>=0\\ x_0 = 1\\ x_2=14 $$ to $$ x_{n} = 14x_{n-1} - 49x_{n-2} + n7^n\\ n>=2\\ x_0 = 1\\ x_2=14 $$ And it's same? I need to find solutions of recursive equations, but have no idea how do it when…
KanekiSenpai
  • 29
0
votes
3 answers

Recursion Relation - Solution

Consider the relation $$p_x + p_{x-1}p_{x} = p_{x-1}$$ with $p_1$ given. The solution is written $$\frac{1}{p_x} = \frac{1}{p_1} + (x-1)$$ in my lecture notes as though trivial. I can't seem to get it. I have tried to re-arrange the main…
PhysicsMathsLove
  • 3,142
  • 1
  • 21
  • 39
0
votes
1 answer

Recurrency procedure for carpet

I try defined recurrency procedure for this shape: I know that if n==0 then we need plot square. But clockwise? Next is plot smaller square, but I have a problem with a tour around the square. My procedure should be allowed for a variable number of…
Blabla
  • 857
  • 6
  • 13
0
votes
2 answers

Simplify formula of a recursive algorithm

I am a software developer, had maths 15 years ago (so I beg for forgiveness if my notation below hurts your eyes), and would like to calculate the number of elements a certain algorithm will produce. The algorithm is implemented, works fine, and I…
wujek
  • 103
0
votes
0 answers

In this set of rules, is the x in s(x) identical with the x in p(x) or are these two different variables?

In this set of rules, is the x in s(x) identical with the x in p(x) or are these two different variables? I didn't find an answer and how to actually search it.
Doy D
0
votes
1 answer

Is upper bound recursive function always primitive-recursive as well?

If there is a constant upper bound for a function which is recursive is it enough to prove that the function is primitive-recursive? I saw this cause disagreements on whether or not the inverse Ackermann function is primitive-recursive or not.
dzi
  • 123
0
votes
0 answers

Write minimum 10 elements from the set $A$

Write minimum 10 elements from the set $A$ defined recursively as follow $$\begin{cases} {1\in A, 2\in A, 3\in A}\\ {x+6\in A, x\in A}\end{cases}$$
brisk tuti
  • 11
0
votes
1 answer

Markov and Recursive Probability with Octahedron

You have 2 people starting on opposite sides of an octahedron, each move to a random vertex each turn. you win by moving onto the vertex of the other person, what's the probability the guy who goes first wins. How I currently attacked…
user690808
  • 157
0
votes
1 answer

How do I apply floor( ) and ceiling( ) to a log(x) correctly?

I am attempting to work out, by using a manual method, how to apply the floor() and ceiling() functions to log2(2096) (2096 is used as an example). My understanding is this (and I am very much a beginner): First, by using a scientific calculator…
Switchkick
  • 103
0
votes
3 answers

Find an expression for Sn+1 in terms of Sn and Sn-1 which holds for all n >= 2

Let Sn be the number of ternary strings of length n in which every 1 is followed immediately by a 2 (these strings cannot end with a 1). Find an expression for Sn+1 in terms of Sn and Sn-1 which holds for all n >= 2. I have no idea how to solve…
llamaro25
  • 289
0
votes
3 answers

How to get a general rule from the recursive definition

Assume we have an arithmetic sequence $f_n$ that has a non-recursive definition as follows: $$f_n=2n+1$$ This sequence can also be defined recursively: $$f_n=2+f_{n-1}$$ $$f_0=1$$ The same can be done if we assume f_n is a geometric…
usuyus22
  • 37
1 2 3
…
12 13