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
0answers
36 views

I Need Helping Understanding a Case of this Recurrence Relation. I am Stumped

I came across this question in my textbook and it is stumping me. Namely, what is stumping me is the final two cases when creating the recurrance relation. I sort of understand that you have to take ...
0
votes
1answer
50 views

Why is minimization (always) effectively computable?

Please excuse me if my question is stupid or obvious, but I don't understand why minimization (in recursion theory) defined as: $$\operatorname{Mn}[f](x_1,\ldots,x_n)=\begin{cases} y,&\text{if }f(...
1
vote
2answers
96 views

Number of ways to color in a $2\times5$ grid

How many ways are there to color in each unit square of a $2\times5$ grid red or blue so that no $2\times2$ square is allowed to be the same color? So I thought about doing an inclusion-exclusion ...
1
vote
2answers
75 views

Finding the closed-form formula to a recurrence with summation of terms

I am currently trying to work through this recurrence problem but am having a hard time coming up with the solution: $g\left(n\right)=\left(\sum_{i=1}^{n-1}g\left(i\right)g\left(n-i\right)\right)+1$ ...
3
votes
2answers
61 views

A die is thrown $n$ times. What is the probability that $6$ appears even number of times?

A die is thrown $n$ times. What is the probability that $6$ appears even number of times (for the purpose of task $0$ is even number)? The solution from my textbook is: We have two hypotheses $H_1$ ...
0
votes
2answers
19 views

coefficient by $x^{n-1}$ in Chebyshew polynominals

Calculate coefficient by $x^{n-1}$ in Chebyshew polynominal of the first kind $T_n$, defined as: $$ T_0(x)=1\\ T_1(x)=x\\ T_n(x)=2x\cdot T_{n-1}(x)-T_{n-2}(x) $$
1
vote
2answers
32 views

Recursive formula, eigenvalue problem

A sequence $ \{X_i \}_{i \geq 0} $ is defined recursive by $ X_{n+1} = 3 X_{n} - 2X_{n-1}, \qquad n \geq1. $  and $ X_0 = \begin{pmatrix} 1 & 0 \newline 1 & 1 \end{pmatrix},X_1 = \begin{...
1
vote
2answers
83 views

Find all functions $f$ such that for all positive integers $x$, $y$, $f(xy)+f(x+y)=f(x)f(y)+1$.

Find all functions $f$ such that for all positive integers $x$, $y$, $$f(xy)+f(x+y)=f(x)f(y)+1\,.$$ I'm pretty sure that the only function that satisfies this equation in $f(x)=1$. By considering $f$ ...
0
votes
2answers
31 views

Finding recurrence relationship involving alternating coefficients

I'm trying to express the following recursive relationship as a summation \begin{align} a_2 &= \frac{-\alpha(\alpha+1)}{2!}a_0 \\ a_4 &= \frac{\alpha(\alpha+1)(\alpha-2)(\alpha+3)}{4!}a_0 \\ ...
0
votes
1answer
42 views

Substitution Method to Prove Inequalities for Recurrence [duplicate]

Use the substitution method to show that recurrence T(n) = T(n-1) + n + 1 implies that T(n) ≤ C * n^2 as long as ...
0
votes
1answer
32 views

Inductive Proof, given $T(n) = \frac 25 T_{n-1} +\frac 35 T_{n-2},\; T_0 = 0, T_1=1$… [closed]

I have the following recurrence relation: $T(n) = \dfrac{2}{5} \times T(n-1) + \dfrac{3}{5} \times T(n-2)$ with base cases: $T(0) = 0$ & $T(1) = 1$ I need help proving, by induction, that ...
1
vote
1answer
44 views

Could anyone solve this challenge problem on series, very similar to the Fibonacci Sequence? an = an-1 + an-2 - an-3.

It is given that a1 = $0.2$, a2 = $0.3$, a3 = $0.5$ and an = an-1 + an-2 - an-3 P = a2013 Q = a1 + a2 + a3 + ... + a2013 R is the minimum value of i such that ai > 2013. S is the number of ...
0
votes
2answers
50 views

How to find a non-recursive formula for a recursively defined sequence

Given: $\mu(0)=0$ $\mu(i)= 2\mu(i-1) + 2^{i-1} \ \ \ \ \ \ \forall i \in N $ I would like to know if there is any way of obtaining the non recursive formula for $\mu (i)$: $\mu(i) = i2^{i-1}$ ...
0
votes
1answer
26 views

Derive a recursion formula for integral

Let $$I_n=\int_{-1}^1(1-x^2)^ndx.$$Use integration by parts to derive a recursion relation for the integral. After I used integration by parts the answer I got was $$\left.x(1-x^2)^n\rule{0mm}{6mm}\...
0
votes
0answers
31 views

Find a recursive formula for $a_n$, $n ≥ 2$, in terms of $a_{n−1}$ and $a_{n−2}$, where $a_0 = 0, a_1 = 1$

Find a recursive formula for $a_n$, $n\ge 2$, in terms of $a_{n-1}$ and $a_{n-2}$, where $a_0=0$, $a_1=1$, $a_2=-1$. The power series is $$\sum\frac{(-1)^{n-1}}{(n-1)!}$$ And can anyone help with ...
1
vote
1answer
44 views

Counting number of points on plane in special procedure

Lets define following function $f : \mathbb{N} \rightarrow \mathbb{N}$ First consider arbitraty four points on plane $\mathbb{R}^{2}$, that are corner of some square. We write then $f(1)=4$ Later we ...
1
vote
1answer
34 views

Can someone help me prove the following proposition?

Let S be the set of positive integers defined by Basis step: 1 ∈ S. Recursive step: If n ∈ S, then 3n + 2 ∈ S and n^2 ∈ S. a) Show that if n ∈ S, then n ≡ 1 (mod 4). b) Show that there exists an ...
1
vote
1answer
39 views

Recursive L'Hospital's rule

Is it possible to prove that if: $$\lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} =\lim_{x\rightarrow\infty} \frac{f(x)}{g(x)}\frac{1}{l(x)}, \quad\text{and}\quad \lim_{x\rightarrow\infty}\frac{1}{l(x)}...
-3
votes
2answers
85 views

Elementary Combinatorics+Graph Olympic Problem [closed]

In the city there was one person infected with a virus. Every day every sick person is visited by all his healthy friends, they become infected with the virus and get sick the next day. And all ...
2
votes
1answer
25 views

How to prove that a recursive function is equal to another formula?

Define recursively b sub 0 = 1 and for n > 0, let b sub n = 3b sub (n−1) − 1. Prove by induction the formula holds: b sub n =(3^(n)+1)/2. I started out with a basis: Let n=1 We get that 2=2 ...
1
vote
0answers
25 views

For any odd positive integer $n$, there is a recursive binary tree that has depth at most $\log_2(n)$ - why?

In chapter 7 of "Mathematics for Computer Science" (Lehman, Leighton, Meyers, 2018), I have a doubt concerning a theorem about binary trees. Relevant definitions Before going into the ...
1
vote
2answers
30 views

How do I derive a general formula for $I(n,m)$?

To prove the first one, here's what I did: $\int x^nln(x)^mdx=$ IBP: $ln(x)^m=u \Rightarrow \frac{mln(x)^{m-1}}{x}dx=du$ $x^ndx=dv \Rightarrow v=\frac{x^{n+1}}{n+1}$ $\Rightarrow$ $$ln(x)^m\frac{...
0
votes
1answer
37 views

Markov chain recurrence solving

I am given a transition matrix for the markov chain on the space state $X=\{1,2\}$ $P=\begin{pmatrix} 1-a & a\\ b & 1-b \end{pmatrix}$ We are asked to find $P^n$ as a hint I am told to notice ...
1
vote
2answers
41 views

Solving Knapsack with Multiple Constraints and Return nth Best Results

Example Data For this question, let's assume the following items: Items: Apple, Banana, Carrot, Steak, Onion Values: 2, 2, 4, 5, 3 Weights: 3, 1, 3, 4, 2 Max Weight: 7 Objective: My goal is to ...
2
votes
1answer
33 views

General Structuring of Recursive Induction

I'm currently learning recursive induction, but I'm really struggling on how to do recursive induction questions. I'm fine with normal induction (i.e. prove that $1+2+3+...+n=\frac{n(n+1)}2$, and ...
3
votes
1answer
74 views

A question about the plastic number

The plastic number is well known to be the limiting ratio of the Padovan sequence (OEIS A000931), to wit, $$ P_n=P_{n-2}+P_{n-3}\\ \lim_{n\to \infty} \frac{P_{n+1}}{P_n}=p $$ However, it is also the ...
1
vote
0answers
28 views

Computing an average of many sums by dynamic programming (?)

Let $N$ be a large integer, let $x_1, \ldots, x_{2N}$ be a subset of some space $\mathcal{X}$ (the details of which are irrelevant), and let $f, g, h$ be functions mapping $\mathcal{X}$ to $(0, \infty)...
0
votes
1answer
40 views
3
votes
3answers
54 views

Find sum of consecutive triangular number recursively

In Computer Science, I was asked to write a program that finds the sum of (1 to n)th triangular number, where n is a positive integer. If n=1, result is 1 If n=2, result is (1) + (1 + 2) By testing ...
0
votes
2answers
34 views

What is wrong with my solution for this recurrence relation with non-constant coefficients: $a_n = \frac{x}{n} \left( a_{n-1} + a_{n-2} \right)$?

Let the following recurrence relation with non-constant coefficients be defined: $a_0 = 1$ $a_1 = x$ $a_n = \frac{x}{n} \left( a_{n-1} + a_{n-2} \right)$ My attempt: Let's define our target ...
0
votes
1answer
25 views

How to show that $b_n(n) \neq 0$ for $b_n(x) = -\frac{16 x}{n} b_{n-1}(x) - \frac{48 x}{n} b_{n-2}(x)$?

Lets define the recursive polynomial: $b_0(x) = 1$ $b_1(x) = -16 x$ $b_n(x) = -\frac{16 x}{n} \left( b_{n-1}(x) + 3 b_{n-2}(x) \right) = -\frac{16 x}{n} b_{n-1}(x) - \frac{48 x}{n} b_{n-2}(x)$ ; ...
1
vote
0answers
15 views

Tessellated space defines a recursive set?

Is a space which has a regular geometric pattern necessarily a recursive set? It's obvious, for example, that $\mathbb{Z}^3$ is a recursive set and it has a "regular geometric pattern", so this ...
1
vote
1answer
33 views

Finding closed form of Fibonacci Sequence using limited information

I'm trying to find the closed form of the Fibonacci recurrence but, out of curiosity, in a particular way with limited starting information. I am aware that the Fibonacci recurrence can be solved ...
1
vote
0answers
71 views

Find asymptotic boundary of recursion with sum

Given $T(n) = \left( \sum_{i=1}^{\log n} T(\lfloor \frac {n}{k^i} \rfloor) \right) + n $ where $k \ge 3$, how do I prove that $T(n) = \theta(n) $? I tried replacing $n$ with $2^m$ when $m = \log n$ ...
1
vote
1answer
56 views

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 ...
0
votes
2answers
57 views

Fibonacci's rabbits variation

In this variation on Fibonacci rabbits the growth of mature rabbits in a period has to be less than 10%. After one period the rabbits are called "young rabbits", after two periods the rabbits will ...
0
votes
2answers
23 views

Recursively prove that two recursively defined sets are the same

I am reading MIT's Mathematics for Computer Science, and there is a problem where you're asked to prove that two recursively defined sets are the same. I'm not sure how to go about mutual inclusion ...
-1
votes
1answer
37 views

Solving the recurrence $T(n) = 3T(n/4) + n\log n , T(1) = 1$ [closed]

Solve the recurrence $T(n) = 3T(n/4) + n\log n , T(1) = 1$ Can someone help me to solve this recurrence using substitution method?
1
vote
1answer
49 views

finding a formula for the generating function for a recurring sequence

I have the sequence $a_0=0$, $a_1=3$, $a_2=0$, $a_3=23$, and $a_n=6a_{n-2} + 8a_{n-3} + 3a_{n-4}$ for $n\ge 4$ and I have to find the formula for the generating function $A(t)=\sum_{n=0}^\...
0
votes
0answers
19 views

Recursion relation for the expansion coefficients of the product of two Jacobi polynomials in terms of one Jacobi polynomial

I need the recursion relation satisfied by the expansion coefficients $\left\{ {{c_k}} \right\}$ in the following series: $P_n^{(\mu ,\nu )}(x)P_m^{(\mu ,\nu )}(x) = \sum\limits_{k = \left| {n - m} \...
0
votes
1answer
32 views

Set up a summation notation from a sequence

I want to set up a summation notation for numbers of blocks that is needed in a podium with n layers but I dont know how to do that. I calculated the following sequence: first layer: 9 blocks second ...
-1
votes
1answer
31 views

Set up a rule from a pattern [closed]

I have to set up a recursive formula for a sequence that gives the number of ways to take out and arrange lego bricks to a wall with the length of 2n knobs. Some lego bricks have 6-knobs and some ...
0
votes
1answer
48 views

How many repeated steps in a Fibonacci recursive function [closed]

how can i calculate how many repeated calls occur in a fib recursive function. fib(n): if n = 0 : ret 0 if n = 1 : ret 1 ret fib(n - 1) + fib(n - 2) ex) if n = 5 how many times fib(...
0
votes
1answer
29 views

Exact number of steps in a recursion [closed]

I am studying algorithms and I came across this problem: $t(1) = 1$ and $t(n) = 4t(n/2) + n^2$ Calculate the exact value of $t(n)$ for all $n=2^l, l \in N $ Initially I thought this would be a ...
0
votes
1answer
48 views

Building palisade with lego bricks

I have problem solving the following questions: I have infinite amount of lego bricks with 6 and 8 knobs in length. I want to build a palisade that has the length of 48 knobs. In what ways can I ...
1
vote
2answers
68 views

Where does this recursion formula come from?

I come across an explanation of recursion complexity. This screenshot is in question: How do you get this? T(n) = 3T(n/4) + n The $log_n^4$ shown seems to be ...
2
votes
1answer
26 views

Find the probability that the 2nd and 3rd order statistics are compared in the QuickSelect algorithm

A description of QuickSelect: In the selection problem, we have a list of numbers and want to find the ith order statistic. That's the ith smallest value, which is the value such that i-1 other ...
0
votes
1answer
444 views

sum of numbers in 2D list using recursion

The matrix above is represented like this in Python: m = [[2, 1, 3], [4, 9, 8], [6, 2, 7]] The function should return the following output 2D ...
1
vote
2answers
106 views

recurrence initial conditions

I'm working on a homework assignment involving recursion and I'm having trouble finding an easy way to determine the initial conditions. Heres the problem: We want to tile ann×1 strip with tiles of ...
2
votes
1answer
104 views

Does this infinite sum with recursively defined coefficients converge?

Consider the following two series: $$a^{(0)}_n,\;\; n = 1,2,...,N \;\;\text{and}\;\; c_m,\;\; m=1,2,...,M$$ where both satisfy: $$\sum \limits_{n=1}^{N}a^{(0)}_n = 1 \;\; \text{and}\;\; \sum \...

1 2
3
4 5
42