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
1
vote
1 answer

Solving Recursions like this

How can i solve this equation? I am really stuck $T(n) = T(n + 1) + T(n + 2) + 3n + 1$ $T(0)=2$ $T(1)=3$
Mario
  • 127
1
vote
2 answers

Simple recursive equation sub-solution: $T(n) = (n+2) + \sum^{n-1}_{i=0}T(i)\\ T(0) = 1$

I have tried to solve a very simple recursive equation:))), but I don't know what's wrong with my brain but I got other solution when I partially solve the equation. Equation: $$T(n) = (n+2) + \sum^{n-1}_{i=0}T(i)\\ T(0) = 1$$ What I've tried: $T(n)…
Tatar Elemér
  • 276
1
vote
2 answers

help in solving a recursion

EDIT: Turns out that the given solution has an error in it. I have the following recursion question and following that is my answer. The problem is it doesn't seem to agree with the marking scheme. Can you help me by pointing out where i have gone…
Krimson
  • 591
1
vote
2 answers

Solving for $\omega_i$ given the recursive sequence $\omega_{i + 1} = \frac{7}{13}\omega_i + \frac{6}{13}\frac{v}{r}$ and $\omega_0 = 0$.

I am having trouble solving this recursive sequence $$\omega_{i + 1} = \frac{7}{13}\omega_i + \frac{6}{13}\frac{v}{r}$$ given that $\omega_0 = 0$. I tried using Engineer's Induction but all it's leading to are messy fractions.
WwW
  • 161
1
vote
1 answer

Simplifying a recursive expression

Let $p_n = \frac{1}{6}\left(p_{n-1} + p_{n-2} + p_{n-3} + p_{n-4} + p_{n-5} + p_{n-6} \right)$. Let $p_0 = 1$ and $p_k = 0$ for $k < 0$. Using this recursive equation, is there a simple way to obtain the following expressions, in particular for…
Gaussian0617
  • 704
1
vote
2 answers

$T(n) = 2T(n-2) + 1$ recursion tree

Can someone help me build what the recursion tree would look like for this problem? Would the next level be $n-3$, and then $n-4$?
Lucy Jones
  • 23
1
vote
2 answers

General query about Lucas Sequence

Lucas Sequence with 1 and 3 as initial values Why is it convention to have recursive sequences like the Fibonacci and Lucas numbers start at 0? For example Fibonacci Sequence has $F_{0} = 0$, $F_{1} = 1$ and $F_{2} = 1$, whilst Lucas's sequence has…
Thomas Farkas
  • 11
1
vote
2 answers

How to find an explicit formula for $d _ k$

Consider sequence $ d _ 1, d _2, d_3 $ $$d_k= \frac {d_{k-1}} {k + 1} $$ for all integers $k \ge 2 $ with the initial condition that $ d_1 = 1$. Find an explicit formula for $d_k$ for the $k^{th}$ term. So far I have figured out $d_1 = 1, d_2 =…
Max
  • 55
1
vote
1 answer

Prove solution for homogeneous difference equation with repeated roots

Sorry for this dumb question, but I need help finding an error in my proof. Assume you have a difference equation $$u_{n+1} + au_n + bu_{n-1} = 0.$$ We assume the solution is $$A \lambda^{n+1} + aA\lambda^n + bA\lambda^{n-1}.$$ Then the auxiliary…
Hinton
  • 167
1
vote
0 answers

Find non-identical matrices such that one cannot be converted into another by rearranging rows and then columns (Counting problem)

Given $N \times M$ binary matrices (matrix containing only $0$'s and $1$'s), two matrices are called identical if one can be converted into the other by first permuting the $N$ rows and then permuting the $M$ columns of the resulting matrix. Find…
Mathejunior
  • 3,344
1
vote
0 answers

Find recursion rule after n

i have a quite complicated formula in d dimensions and i am trying to find a recursion rule by $n$ for it. $S^d_n = \displaystyle \sum_{j_1,\dotsc,j_{d-1} \in \mathbb{N}_0\\ \sum_{i=1}^{d-1}j_i \leq n} \sum_{i_1,\dotsc,i_{d-1} \in \{0,1\}}…
matosch
  • 37
1
vote
3 answers

Solve the recurrence $T(n) = T(n-1) + 2T(n-2) + 2$

$T(0) = 1, T(1) = 0$ I ain't able to get answer from any of the methods. Substitution: $T(n) = x^n $ \begin{align} & x^n = x^{n-1} + 2x^{n-2} + 2 \\ & x^2 = x + 2 + 2x^2\\ & x^2 + x + 2 =0 \end{align} solving this I will get a complex…
Pygirl
  • 199
1
vote
2 answers

What is the recursive definition of $f(n)=1+(-1)^n$ for $n≥1$? I think it's:

What is the recursive definition of $f(n)=1+(-1)^n$ for $n≥1$? I think it's: 1) $f(1)=0$ 2) $f(n)=f(n-1)+2$ if $n$ is even $f(n)=f(n-1)-2$ if $n$ is odd Is it correct?
user560980
  • 71
1
vote
3 answers

Recursion: $f(n+1)=-2f(n)$

Given the function defined recursively as: $f(n+1)=-2f(n)$ $f(0)=3$ How can I find $f(5)$ using the recursion?
user560980
  • 71
1
vote
2 answers

What is wrong with the attempts at defining a Recursive Function

What is wrong with these attempts at defining a recursive function? (i) $f(0) = 0, f(1) = 1, f(2) = 1, f(3) = 3, f(n) = f(n - 1) + f(n - 2)$ $\quad$$for \ n \ge 2$ (ii) $f(0) = 0, f(n) = f(n - 1) + f(n - 2)$ $\quad$$for \ n \ge 2$
jhg
  • 77
1 2 3
…
12 13