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

Filter by
Sorted by
Tagged with
1
vote
2answers
63 views

Solving recursive function with floor

The recursive function is this: $$ T(n) = \begin{cases} 2 & \text{ for }n=1;\\ T \left( \lfloor \frac{n}{2} \rfloor \right) + 7 &,\text{ otherwise} \end{cases} $$ Based on the definition of ...
0
votes
1answer
27 views

Statistics/Discrete Math Recurrence Questions - which of the following are true for integers… [closed]

Can someone explain why the answer for 12 is d) and why the answer for 13 is b)? I'm trying to study for a test tomorrow but I'm looking over the answers for this practice test and I genuinely don't ...
2
votes
0answers
52 views

2-cycle and eventually fixed point at periodic point problem

Given $f(x) = x^2-1$. Prove that the basin of attraction of the 2-cycle $\{-1,0\}$ consists of all numbers in the interval $\left(\frac{1-\sqrt5}2, \frac{1+\sqrt5}2\right)$, except for the points ...
-1
votes
1answer
28 views

proof problem of Period 3 point of a function

Let $f(x) = 1/(1-x)$. Show that if x ≠ 0,1, then $x$ is a period 3 point. What I did was I took the 3rd iterate $f^3(x) = f(f(f(x)=x$, ie I took $ -\frac{1-\frac{1}{1-x}}{\frac{1}{1-x}}$ and when ...
0
votes
1answer
51 views

Is it 2 cycle attracting?

Let $c$ be a constant and let $f(x) = x^3-3x+c$, $c>0$. Determine the values of c for which ${0,c}$ is a 2-cycle. Is the 2-cycle attracting for the value of $c$? Explain. I am having trouble ...
-1
votes
2answers
40 views

Verifying a Recursion Formula

I am attempting to prove the equation at the bottom of the image, or simply verify that it is a true mathematical relationship. I have computed a(3) and, in the latter part of the question, found the ...
0
votes
1answer
44 views

How to show that a function is recursive?

I have a problem for the comprehension of how to prove that a function $ log_2 : \mathbb{N} \rightarrow \mathbb{N}$ defined as: $$log_2 (x)= \begin{cases} y & \text{if $x=2^y$} \newline \bot &...
0
votes
1answer
34 views

Step by step conversion from recursive function to closed-form

Currently, I'm interested about Pascal's triangle and binomial coefficients. To train my skills in programming, I plotted a Pascal triangle using only its image. So, I got a beautiful recursive ...
0
votes
0answers
18 views

Recursion Logic Problem Grammar

$S$ is the set of all valid fully parenthesized expressions that can be formed using the variable symbols $x$ and $y$, the unary function symbol $f$, the binary function symbol $g$, parentheses, ...
0
votes
0answers
10 views

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.
1
vote
1answer
75 views

About $A_{n+1}=A_{n}+A_{n}^{2}$ and OEIS $A122888$

OEIS A122888 is: $1, 1, 1, 1, 2, 2, 1, 1, 3, 6, 9, 10, 8, 4, 1, 1, 4, 12, 30, 64, 118, 188, 258, 302, 298, 244, 162, 84, 32, 8, 1, 1, 5, 20, 70, 220, 630, 1656,\dots$ I'm having trouble ...
0
votes
1answer
37 views

Numerical methods, show that wave equation expression is constant

$\newcommand{\pd}[2]{\frac{\partial#1}{\partial#2}} \newcommand{\IR}{\Bbb R}\newcommand{\dd}{\mathrm{d}}$ The wave equation: $$ \pd{^2u}{t^2}(x,t)=c^2\pd{^2u}{x^2}(x,t),~~ t>0,~x\in(0,1)\tag4 $$ ...
0
votes
1answer
63 views

If $\phi:X\rightarrow Y$ is a function then $|\phi(X)|\le|X|$?

Using the Axiom of Choice we know that any set $X$ is equipotent to an unique initial ordinal $|X|$ that we call the cardinal of $X$, so we can organize the elements of $X$ in a transfinite succession,...
2
votes
4answers
64 views

Prove $a_n=\frac{(2^{n-1}+1)a_1-2^{n-1}+1}{2^{n-1}+1-(2^{n-1}-1)a_1}$ for the recursive sequence $a_{n+1}=\frac{3a_n-1}{3-a_n}$

Prove the statement: $$a_n=\frac{(2^{n-1}+1)a_1-2^{n-1}+1}{2^{n-1}+1-(2^{n-1}-1)a_1}$$ for the given recursive sequence: $$a_{n+1}=\frac{3a_n-1}{3-a_n}. $$ My attempt: Proof by induction: (...
0
votes
0answers
26 views

Explicit form of the logistic map

Recently I've been attempting to write and explicit form of the logistic map: $x_{n+1} = rx_n(1-x_n)$ where $x$ is between $0$ and $1$ It's a pretty simple equation, but I was curious if it was ...
1
vote
1answer
87 views

What is the math behind this Python program generating multinomial coefficients?

I wrote a Python program that is using recursion to generate multinomial coefficients - see next section. Mathematically it is also using recursion by 'decrementing down to the boundary'. My ...
0
votes
2answers
39 views

$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$?
1
vote
2answers
32 views

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} =...
3
votes
1answer
111 views

Convergence and limit for Collatz type of recurrence

Let $x_0=1$ and $$x_{n+1}= 2+3\cdot\frac{x_n}{2} \mbox{ if } x_n \mbox{ is even}, $$ $$x_{n+1}= 1+3\cdot x_n \mbox{ otherwise}.$$ Let $$z_n = \frac{\log x_n}{n}.$$ I have numerous questions ...
0
votes
1answer
34 views

Finding limit and monotone in recursive function…

I have a recursive string $\displaystyle C_1 = 10, \quad C_{n+1}=4-\frac{4}{C_n}, \quad n>0.$ How can I find the limit, $\lim_{ n\rightarrow\infty}C_n$ of this recursive function? Also, would ...
0
votes
1answer
91 views

Recursive Sequence $2a_{n+1}=a_n^2+1$

In sequence $\{a_n\}$, $a_1=2$ and $2a_{n+1}=a_n^2+1$, define $b_n=\cfrac{2a_n-1}{a_n+1}$, if $$b_1+b_2+\cdots+b_{2019}>t$$find the max integer t. I find it is nearly impossible to find the ...
0
votes
1answer
69 views

Number of ways to pick the elements of an array?

How to formulate this as a DP problem? Problem Statement: Find the number of ways to pick the element from the array which are not visited. We starting from 1,2,.....,n with some (1<= x <=...
1
vote
1answer
41 views

How to prove that $\bigcup_{\nu<\theta}\alpha_\nu=\bigcup_{\nu<\theta}[\alpha_\nu\setminus(\bigcup_{\xi<\nu}\alpha_\xi)]$?

Perhaps using transfinite induction I managed to prove that $$\bigcup_{\nu<\theta}\alpha_\nu=\bigcup_{\nu<\theta} \left[ \alpha_\nu\setminus \left( \bigcup_{\xi<\nu} \alpha_\xi \right) \right]...
0
votes
0answers
34 views

Calculating the odds of selecting a group, then a specific element of a group

It's been a while since I took probabilities and statistics in school, so I wouldn't be too surprised if this is simpler than I thought but I haven't had much luck figuring it out so far. Lets say you ...
0
votes
1answer
23 views

Is there an upper bound to the amount of distinct fractions in an egyptian fraction?

We know that any fraction $\dfrac mn$ with $m < n$ can be expressed as a finite number of terms $\dfrac1{x_1} + \dfrac1{x_2} + \cdots + \frac1{x_n}$, using the recursive algorithm $\dfrac mn - \...
3
votes
2answers
67 views

How to solve recursive equations when there are two different conditions on recursion?

This was a problem asked in a coding competition at CodeChef and I asked it before on math stack exchange but unknowingly during the competition as I was not aware of the norms before. As the contest ...
0
votes
1answer
66 views

Recursion: How many additions are needed to calculate the n-th Fibonacci number?

If the Fibonacci numbers are given by $F_n = F_{n-1} + F_{n-2}$, find and solve a recursion for the amount of additions needed to calculate the n-th Fibonacci number. I think i've figured out the ...
0
votes
0answers
10 views

How do coalgebra eliminators work?

I've been reading about coalgebraic data types, and I've got the impression that they are dual to algebraic data types in that while ADTs are defined in terms of constructors (and terms are built ...
0
votes
0answers
34 views

Formal definition of computation according to Jech's “Introduction to Set Theory”

Formal definition of computation according to Jech's "Introduction to Set Theory" I'm trying to formally define the concept of a computation according to Jech's Book. First he states the Recursion ...
0
votes
0answers
59 views

Is this a valid function. Translating Haskell code to pure maths

I am currently learning Haskell and I wrote a tail recusive function to find the sum of some list. I wanted to try and write it out in pure maths, transalating as closely as I can what I did in ...
1
vote
1answer
46 views

why is $g(x)=\phi(x,x)$ still a recursive function

I'm reading this book, logic and complexity by Richard Lassaigne, where there is a recursive function $\phi(x,y)$ which enumerates all the recursive functions with one parameter (for the sake of this ...
2
votes
4answers
37 views

Recursive sequence calculation

So I have a finite sequence with K+1 terms .I'm trying to rewrite the following recursive sequence as a general term: $ a_{n+1} = 2a_n -a_{n-1} $ given $ a_0 = 1 , a_K =0$ Would love to know if ...
2
votes
3answers
60 views

Proving recursive function outputs $2^x \cdot {x \choose y}$

Consider following function $f: \mathbb{N}\times\mathbb{N} \rightarrow \mathbb{N}$: \begin{align*} f(x ,y) = \begin{cases} 0 & \text{if } x < y\\ 2^x & \text{if } y = 0\\ 2 \cdot (...
1
vote
1answer
49 views

using proposition for double induction

I want to use double induction (induction on two variables, right?) and I'm unsure of how to use the proposition for recursive functions. For a double induction I figured I needed two proofs, one for $...
3
votes
3answers
74 views

You started with one chip. You need to get 4 chips to win. What is the probability that you will win?

This is very similar to the question I've just asked, except now the requirement is to gain $4$ chips to win (instead of $3$) The game is: You start with one chip. You flip a fair coin. If it ...
2
votes
2answers
52 views

Given that you started with one chip, what is the probability that you will win this game?

The game is: You start with one chip. You flip a fair coin. If it throws heads, you gain one chip. If it throws tails, you lose one chip. If you have zero chips, you lose the game. If you have ...
1
vote
1answer
28 views

Why does probability recursion not work in this case? “What is the probability that the person who makes the first roll wins the game?”

So the first example (where recursion works) the author provided is You play a dice game with a friend. You roll a fair 6-sided die and your friend rolls a fair 8-sided die. You add $2$ to your ...
1
vote
1answer
52 views

Sum index in a Recursive Procedure Call in Maple

I'm trying to reproduce Buchholz Polynomials in Maple as outlined by J. Sesma and J. Abad in their paper (equation 14). The definition given above is a recursive one and so is the code I've created ...
0
votes
0answers
21 views

Developing a recursive formula for probability problem? [duplicate]

I'm trying to figure out the following problem from Bertsekas & Tsitsiklis' Introduction to Probability, 2nd edition: Two players take turns removing a ball from a jar that initially contains ...
0
votes
1answer
21 views

linear homogeneous recursion roots second degree

This is just a random example, I just wonder how to solve linear homogeneous recursion relations. If we say that $b_n = b_{n−1} + 2b_{n−2}$ and $b_1 = 1$ and $b_2 = 2$, how do I find the equation for ...
1
vote
0answers
36 views

Counting bit sequences

Suppose we are to count bit sequences of length $n$ s.t the sequence doesn't contain 3 consecutive 1's If $P(n)$ is the number of such sequences, is the equality $P(n) = P(n-1) + P(n-2) + P(n-3)$ ...
3
votes
3answers
76 views

recursive succession $a_{n+1}=\frac{a_n+2}{3a_n+2}, a_0>0$

I'm given this recursive succession: $a_{n+1}=\frac{a_n+2}{3a_n+2}, a_0>0$. This is what I've done: $L=\frac{L+2}{3L+2} \rightarrow L_1=\frac{2}{3}$ and $L_2=-1$ if $a_0 >0 $ then $a_n>0 ...
26
votes
2answers
666 views

Does this sequence always terminate or enter a cycle?

I've been fiddling with the recursive sequence defined as follows: $$\begin{equation} f_n=\begin{cases} a, & n=1.\\ b, & n=2.\\ c, & n=3.\\ f_{n-1}f_{n-2}f_{n-3} \mod[f_{n-1}+f_{...
3
votes
1answer
200 views

Proving a primitive recursive function

I'm asked to find a primitive recursive formula the function: $$ f: N × N → N, f(n, k) = {n \choose k} $$ My attempt: I know that ‏‏‎ $$ {n \choose k} = \frac{n!}{k! (n-k)!} $$ and so a primitive ...
0
votes
0answers
48 views

Finding a recursive formula for the number of ways to represent a vector in $\mathbb{Z}^2$ as a sum of vectors in $\mathbb{Z}^2$

Let $z=a+bi$, where $a$ and $b$ are non-negative integers. I need to count how many ways are there to represent $z$ as $$z=\sum\limits_{j}a_j+b_ji$$, where $\forall j \ \ a_j\not=0$ or $b_j\not=0$. $...
0
votes
1answer
34 views

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 ...
0
votes
1answer
19 views

Expected value of ticket, when we can also win multiple lottery tickets / re-rolls

Let's start from simplified case, that is trivial to solve, then I wil explain the problem that I have (it's not a homework of any kind or anything, I just want to know expected value of the rewards I ...
1
vote
0answers
29 views

Solve the following recurrence: $E[T(n)] \leq \frac{2}{n} ∑_{k=\left\lfloor\frac{n}{2}\right\rfloor}^{n-1} E[T(k)] + 1$

I am trying to solve the following recurrence but I do not really get how I could do it. Basically the task is very similar to CLRS page. 216-219. I already found the expected number of recursive ...
2
votes
2answers
75 views

Find the $Θ$ of $∑\log\log k$?

I am struggling finding the $$\sum_{k=1}^{n}\log \log k$$ I know that $∑_{k=1}^n \log k = \log(n!) \implies Θ(n\log(n))$. But unfortunately that does me help me to find the $Θ$ for $∑_{k=1}^n \log \...
2
votes
1answer
137 views

Closed form of $\prod_{i=0}^{N}\big(i!\big)^{{N}\choose{i}}$

I was wondering if there is a closed form for $$\prod_{i=0}^{N}\big(i!\big)^{{N}\choose{i}}$$ I know that for $$\prod_{i=0}^{N}\big(i!\big)=G(N+2)$$ where we have expressed it as Barnes G-function. ...

1 2 3
4
5
42