# 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

2,790 questions
Filter by
Sorted by
Tagged with
1 vote
46 views

### $A\subset \mathbb{N}$ and $(A+1)=\{x+1\mid x\in A\}$. how many subsets of $\{1,2,3,\dots, n\}$ exists, such that $A\cup(A+1)=\{1,2,3,\dots, n+1\}$.

Let $A\subset \mathbb{N}$ and $(A+1)=\{x+1\mid x\in A\}$. For every $n$, how many subsets of $\{1,2,3,\dots, n\}$ like $A$ exists, such that $A\cup(A+1)=\{1,2,3,\dots, n+1\}$. My try: As we should ...
7 views

### Recursion on predicate language

Is it possible to write any expression in the language of first-order predicates that would essentially be a recursion, that is, something similar to iteration in a loop?
21 views

### Solve VAR(2) for the n-step ahead forecast

I'm trying to find for this VARX*(2) $$x_t=a_0+a_1t+F_1x_{t-1}+F_2x_{t-2}+\Theta_0d_t+\Theta_1d_{t-1}+\Theta_2d_{t-2}+\varepsilon_t$$ an explicit form for $x_{T+n}$, i.e. solve it as an equation for ...
33 views

### Primitive Recursion Data and Uniqueness

This is an exercise from Lawvere’s Conceptual Mathematics that is stumping me. It relates to constructing a single map from a starting point of primitive recursive data. Any help or tips would be ...
44 views

### Find a recurrence relation for the number of bit strings of length n that contain consecutive symbols that are the same

Here is my attempt: First there is $2 \cdot 2^{n-1}$ ways if string ends with $00$ or $11$. Second there are ways when string end with $10$ or $01$. So it will give us $a(n-1)$ ways to solve ...
128 views

98 views

### Prove that $a_n\ge 1$ for all $n\ge 1$ with equality iff $n=1,2,4,5$

Let $\alpha, \beta,\gamma \in \mathbb{C}$ be the three roots of $x^3 + x+1$. For any $n\in\mathbb{N}$, let $a_n = \dfrac{(\alpha^n-1)(\beta^n-1)(\gamma^n-1)}{(\alpha-1)(\beta-1)(\gamma-1)}$. Prove ...
62 views

### Using generating functions to simplify a recursive solution

This is a follow-on question to my previous one: All the different ways to add a set of lengths - need explanation of the answer I have a problem simplifying a specific recursion relation. I have ...
92 views

### Find a limit of recursion sequence

I have to find a limit of recursion sequence $a_{n}=-\frac{3}{8}(a_{n-1}+a_{n-2})$ where $a_1=1, a_0=0$. I wrote few of first terms of sequence: $0,1,-\frac38,\frac{15}{64},-\frac{57}{8^3}...$ My idea ...
104 views

1 vote
46 views

### How do you set up this recursive system?

Here is the problem: Emma wants to climb a 12-step staircase. She can climb either 1 or 2 steps at a time. In how many ways can she climb the staircase? I first set $F_{n}$ as the number of steps it ...
40 views

### Solution to a first-order rational difference equation [duplicate]

I am interested in the following first-order rational difference equation (recurrence relation): $$x_{n+1} = x_n + \dfrac{\alpha}{x_n} + \beta \ ; \ x_0 >0$$ for positive $\alpha$ and $\beta$. Is ...
39 views

111 views

### Given analytic $F(x)$ find $f(x)$ such that $\forall x. F(x) = f(f(x))$

Many years ago, I worked on the following problem. Given a real analytic function $F(x)$, find a continuously differentiable real function $f(x)$ such that $\forall{x}. F(x) = f(f(x))$. I was able to ...
1 vote
54 views

### Matching problem in a recursive way

Suppose there are $n$ people invited to a party. Seats are assigned and a name card is made for each guest. However, floral arrangements on the table unexpectedly obscure the name cards. When the $n$ ...
99 views

### Identify $d$ heavy coins where $d$ is unknown.

You are given $N$ coins which look identical (assume $N = 2^k$). But actually some of them are pure gold coins (hence are heavy) and the rest are aluminum coins with thin gold plating (light). You are ...
48 views

### Alternative characterisation of supremum

Given a sequence $\{b_j\}_{j\in\mathbb{N}}$, can we define $\alpha_k=\sup_{j\geq k} b_j$ for any $k\in\mathbb{N}$ recursively through $\alpha_j=\max\{b_j,\alpha_{j+1}\}$ for all $j\geq k$? I am able ...
21 views

### How can I represent a decreasing summation which the highest value is the starting value?

I am trying to find the recurrence of $T(n) = 2T(n-1) + n^2$ The answer it's $O(2^n n^2)$ but now I'm trying to find the answer using recursion and all good, but trying to find $T(n-k)$ is killing ...
122 views

1 vote