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 the functions for some inputs in ...

learn more… | top users | synonyms

0
votes
1answer
47 views

Use geometric progression formula to expand generating function into a power series?

I am a software engineer and I am studying combinatorics on my own to enhance my learning. I have been finally starting to get the hang of generating functions, but the following problem below has me ...
0
votes
1answer
32 views

Recursive Definition

Consider the following informal definition for a function calc(x,y) = (0*y) + (1*y) + … + (x*y) For example, we have that calc(2,5) = (0*5) + (1*5) + (2*5) Give a recursive definition for the ...
0
votes
1answer
47 views

Recursive Enumeration of Total Recursive Functions vs Partial Recursive Functions

We have: Primitive Recursive $\subseteq$ Total Recursive Functions $\subseteq$ Partial Recursive Functions There are three points that appear at odds with eachother: 1) The primitive recursive ...
2
votes
2answers
41 views

How to use recurrence to define generating function? How to write generating function as power series?

I am a software engineer teaching myself combinatorics. This problem is destroying me, but I am following what I thought was the appropriate strategy to solve a recurrence. I am also confused as to ...
0
votes
4answers
47 views

Finding the $S_n$ of a recursion

$$\sum_{k=0}^{n} (1+2k+4(k(k+1)))=?$$ In order to find the $S_n$ what methods are best fitted for such problem? Is it possible to use the lemma $\sum_{i=0}^{n} i= {n(n+1)}/2$ and plug in? I tried but ...
2
votes
1answer
18 views

How to prove the recurrence relation for this generating function problem?

I am a software engineer and I am learning combinatorics theory on my own. I recently got stumped by the following problem. Problem Let $a_{0} = 2$ where $a_{n} = 3a_{n-1} - 2$ with $n>0$. ...
0
votes
2answers
35 views

Finding Recursive Definition for the following:

How would i start off to find a recursive definition for $X_{0}$=.19 $X_{1}$=.1919 $X_{2}$=.191919 ... $X_{n+1}$= what goes here?
2
votes
3answers
57 views

Finding the sum of n terms $S_n$ starting from sigma $k=0$

$$\sum_{k=0}^{n} ((4k-3)\cdot 2^k)+4=(2^{n+3}+4)n-7\cdot2^{n+1}+15$$ How? I've tried everything but i don't see it. Any equivalent solutions are also welcome, thanks.
0
votes
2answers
86 views

Finding the nth term of 1, 6, 24, 76,212,…

What different methods of recursion can I use to find the nth term of this recursion? This should be simple but I don't know what I'm missing. Could you demonstrate the method? $n(0)= 1$, $n(1)= 6$, ...
0
votes
2answers
38 views

Solving recurrence using recurrence trees.

I have a recurrence which I know has the solution $O(\lg n)$, it looks like this: $$T(n) = T(\sqrt n) + \lg n$$ If I understand correctly, the recurrence tree method involves looking for the term ...
0
votes
1answer
23 views

Proving recursive formula is an integer

This seems like a trivial question, but I can't seem to wrap my head around the proof using induction. Prove: $a_n=2a_{n-1}+a_{n-2}$, with initial condition $a_0=1$ and $a_1=1$, is an integer for $n ...
1
vote
1answer
21 views

Using rsolve in Maple

I have tried using rsolve in Maple to obtain a recursion formula from an ordinary differential equation with summations. I get Is there some reason for Maple ...
0
votes
1answer
25 views

Recursive writing involving arithmetic progression

I've been trying to figure out this recursion problem but I'm getting stuck trying to find the nth-term sequence for the last recursion. I found one but the second i'm so clueless about. I don't know ...
0
votes
2answers
27 views

How do you formulate an equation that require its own result to replace one of its unknown?

Is the concept of recursion used in Mathematics as it is in computer science? How would you express it in a formula?
0
votes
1answer
47 views

What is the basin of attraction for the attracting fixed point $x_-$ of $f(x) = x^2+c$

Attempt: If $x_-^2+c=x_-$ then $x_-=\dfrac{1-\sqrt{1-4c}}{2}$ which is attracting for $|f(x)|<1$ i.e $-2<c<\dfrac14$. How do I find the set of points $x$ such that the orbit $f^n(x) \to x_-$ ...
-1
votes
1answer
48 views

Time Complexity

Prepping for an exam and wondering whether I correctly calculated the time complexity. Function is given as: $function XYZ(n:integer)\\ begin for\ i:=1 \ do \ 2*n^2 \ do;\\ ...
0
votes
1answer
23 views

Giving recursive definition

I need to give the recursive function of $3n^2$. I'm pretty sure the base case needs to be $3 \cdot 0^2 = 0$, but I don't know where to go from there. Any help is appreciated.
0
votes
1answer
23 views

Factorial Series Written As Recursive Definition

I have a factorial series as shown below: \begin{equation} (2n+1)!~\text{for all $n \geq 0$} \end{equation} And I would like to know if the recursive definition that I wrote is accurate: ...
1
vote
1answer
24 views

Recursive Definition of a Series

I have a series such as the one below: \begin{equation} 2^n(\sum\limits_{i=2}^{n+1}i)\text{ for all $n \geq 1$} \end{equation} I need to write a recursive definition for it. Here's what I have so ...
2
votes
0answers
62 views

Almost sure convergence of a martingale

I just learned martingales (with no depth) and I am working on the following question. Suppose $S_n$ is a a random walk on the integers and at each step, it increases by 1 with probability $p$ or ...
1
vote
2answers
47 views

Proof concerning Fibonacci and recursively defined sequences

The series $(a_n)_{n\in\mathbb{N}}$ is given through $$a_1=1,\quad a_2=\frac{1}{2},\quad a_{n+2}=a_na_{n+1} \quad\text{ for } n\geq1.$$ I want to show that $$a_n = 2^{-f_{n-1}}$$ whereas ...
1
vote
1answer
28 views

How to give a recursive definition and a direct formula and prove that they both are equivalent.

How to give a recursive definition and a direct formula and prove that they both are equivalent. for example, 10,13,16,19,22,25 I know the formula for this is a,a+d,a+2d,a+3d,... ...
0
votes
4answers
59 views

Find the general formula for the sequences

1=1 2+3+4+=1+8 5+6+7+8+9=8+27 10+11+12+13+14+15+16=27+64 Find the formula is suggested by these equations?Prove your answer is correct. I saw this question on practice exam and ...
0
votes
1answer
38 views

given $n$ stairs, how many number of ways can you climb either step up one stair or hop up two?

this is the question given $n$ stairs, how many number of ways can you climb either step up one stair or hop up two? I need to include the number of ways for $n=1$ through $6$ as well. My ...
2
votes
2answers
156 views

Computationally finding roots of a recursive function

I'm having a pretty complex function $h(n,d) = f(n,d) -n$ where $n \in \mathbb{N}$ and $d \in [1,9] \subset \Bbb{R}$. $f(n,d)$ is recursively defined. $$f(n, d) = \begin{cases} n<0\quad f(|n|,d) ...
1
vote
1answer
86 views

How to get nth derivative of $\arcsin x$

I want to calculate the nth derivative of $\arcsin x$. I know $$ \frac{d}{dx}\arcsin x=\frac1{\sqrt{1-x^2}} $$ And $$ \frac{d^n}{dx^n} \frac1{\sqrt{1-x^2}} = \frac{d}{dx} (P_{n-1}(x) ...
0
votes
0answers
12 views

Difficulties in performing recursive functions

must perform some recursive functions, but I have some difficulties, the first is the realization of multiplication, my step by step went like this: ...
1
vote
2answers
46 views

Recursively defined set subset proof

Consider the subset $S$ of the set of integers recursively defined by BASIS STEP: $3 \in S$. RECURSIVE STEP: If $x \in S$ and $y \in S$, then $x+y \in S$. Q: Show that the set $S$ is ...
1
vote
0answers
15 views

nodes equation cant find formula.

Given the level $N$ at which a node $X$ is located in a binary tree, to search for node $X$ according to level-order traversal, we can use the knowledge of level N where $X$ is located to narrow our ...
0
votes
2answers
51 views

Solving a recursion relation

I have the recursion relation $y_{k}=k(2j-k+1)y_{k-1}$ and I would like to solve it to obtain $y_{k}=\frac{k!(2j)!}{(2j-k)!}$. Can you provide some hints on how I might proceed? P.S.: $j$ is a ...
2
votes
2answers
45 views

$a_{n+2} = a_n^2-n\cdot a_{n+1}$ becomes arithmetic series for some special initial condition?

The following series seems to become an arithmetic series $$a_{n+2} = a_n^2-n\cdot a_{n+1}$$ If $$a_1=3, a_2=4$$ $$(a_3=5, a_4=6, ..., a_n = n+2)$$ Can $a_n=n+2$ be derived from the original ...
2
votes
3answers
66 views

How can one solve the tower of hanoi problem if there are discs of similar width in it?

For example a line with '1111' represents a disc with diameter of length 4. Similarly a line with '111' represents a disc with diameter of length 3. Below is the representation of a tower that has 5 ...
0
votes
1answer
32 views

How to show factorial is recursive?

In my textbook Fact : Given recursive $G:\omega^{n}\rightarrow\omega$ and $H:\omega^{2}\times\omega^{n}\rightarrow\omega$ , a function $F:\omega\times\omega^{n}\rightarrow\omega$ defined by ...
2
votes
2answers
31 views

Laplace Transforms

Show that ${\mathcal L} {\lbrace t^{n-\frac{1}{2}}\rbrace}=\frac{(2n-1)!!}{2^n}\frac{1}{s^n} \sqrt{\frac{\pi}{s}}$ My Attempt: ${\mathcal L} {\lbrace ...
0
votes
1answer
15 views

A linear recurrence

If the sequence $a_n$ satisfies $a_n = 2a_{n-1}+1$ for all $n \geq 1$, show that for every $n \geq 0$, we have $a_n+1 = 2^n(a_0+1)$. I thought of letting $a_n = c^n$ and $a^{n-1} = c^{n-1}$ then ...
1
vote
1answer
31 views

at least half of $u_0, u_1, …, u_{n-1}$ are superior to $2u_n$ , show that $u_n$ converges to 0.

Let $(u_n)_{n >= 0}$ a sequence of positive numbers, such as 1) $u_0 =1$ 2) for all integer $n>0$, at least half of the $u_0, u_1, ..., u_{n-1}$ are superior or equals to $2u_n$. Show that ...
0
votes
2answers
39 views

Solving recursive functions

I have come across this problem in lecture slides which i don't understand. In a dice game there are 2 options: 1. play 2. stop If we choose play, we get $4, and then roll the die. If the die rolls ...
1
vote
0answers
22 views

How to show that F is recursive?

In the road to Godel's incompleteness theorem, Problem saying: Show that Frame For $G:\omega\times\omega\times\omega^{n}\rightarrow\omega$ a recursive function, the function ...
0
votes
0answers
22 views

Recursive formula for an integral involving multiple inner products

Motivation: I am trying to form a Bayesian model where I will be performing frequent state-updates. I am seeking to find a recursive formula for a certain quantity that will enable me to perform this ...
0
votes
0answers
23 views

Solve a three term recursion

Consider the recursive function: $$f(a,b,c) = \frac{a}{t}(1-f(b,a-1,c)) + \frac{b}{t}f(a,b-1,c) + \frac{c}{t} f(a+1,b,c-2)$$ where $$t = a + b+c\\f(a,0,0) = 1$$ This arises in the context of game ...
0
votes
0answers
14 views

iterated logarithm on different arguments

So I have this recurrence which I am not able to solve using the master theorem. $r_1=\log x$ and $r_{i}=\alpha \log (2^{r_{i-1}})$ for all $i\geq 2$. I want to deteremine $r_n$ for some $n$. it ...
0
votes
1answer
14 views

Proof that not every computable function over the natural numbers can be described using structural recursion.

I'm reading Bird's Algebra of programming (excelent book so far). It says It is a fact that not every computable function over the natural numbers can be described using structural recursion I ...
0
votes
0answers
14 views

Values of z for which a recursive sequence converges or diverges.

I am currently working on a problem and I at a loss as to where to begin. Consider a recursive sequence x_n, where: x_0 = 0 x_n = z^(x_n-1) I need to find the values of z for which the sequence is ...
1
vote
1answer
113 views

a recurrence relation for mountain permutation

I really dont know where to start? Can you give some hints?
3
votes
1answer
92 views

What lies between primitive recursion and total recursion?

My understanding is that there are total recursive functions that are not primitive recursive, such as the Ackermann function. What classes of functions (or sets) lie between primitive recursion and ...
0
votes
0answers
28 views

Solving $T(n)=T(n-1)+\log n$ with repeated substitution

Solve $T(n)=T(n-1)+\log n, T(1)=1$ using repeated substitution. Substituting back, we have: $T(n) = T(n-i) + log(n-i+1) +... + \log(n-1)+\log(n)$ And for which $i$ we have $n-i=1$? that is ...
0
votes
0answers
33 views

Proof of Master Theorem using Recurrence Relation By Substitution

Question : T(n)=10⋅T($⌈\frac{n}{3}⌉$)+O($n^2$) I have a solution to that problem but it uses other approach. I'd like to use recursion by substitution method but I'm stuck at the last stage. Here's ...
2
votes
0answers
12 views

Naive Euclidean algorithm - average complexity?

Suppose I compute the GCD in a rather simple-minded recursive way: $$ \gcd(a, b) = \begin{cases} \gcd(a, b-a) & \text{ if }{a < b}, \\ \gcd(a-b, b) & \text{ if }{a > b}, \\ a & ...
0
votes
1answer
24 views

How can I write a partial recursive function “maximum(x,y,z)”?

It is quite easy to write a partial recursive function "max(x,y)": 1.substraction1: substraction(x) = if x=0 then 0 else x - 1 @R(z1,i21) 2.substraction2: substraction(x,y) = if x < y then 0 ...
1
vote
2answers
44 views

Showing that a Sequence is defined recursively

How can I show that the sequence is defined recursively? Show that the recursively defined sequence $(x_n)_{n\in\mathbb{N}}$ with $$x_1=1, \qquad\qquad x_{n+1}=\sqrt{6+x_n}$$ converges and ...