Questions regarding functions defined recursively, such as the Fibonacci sequence.

learn more… | top users | synonyms (2)

5
votes
1answer
240 views

two-dimensional recurrence

Can someone using only these conditions $$a_{m,k}=a_{m-1,k}+a_{m-1,k-1},m>k$$ $$a_{m,k}=1,m=k$$ $$a_{m,k}=0,m<k$$ prove that $$a_{m,k}=\frac{m!}{k!(m-k)!}$$ here is way to construct Pascal ...
5
votes
2answers
434 views

Show that the Catalan numbers are given by this recurrence relation

Hey guys! I'm doing an assignment, and I'm just not sure (at all) how to start this problem. Can somebody nudge/shove me in the right directions? Show that the Catalan numbers are given by the ...
5
votes
1answer
111 views

What is the expected number of questions answered to complete a sequence in which wrong answers send you to the start?

Given a sequence of n questions that each contain x answer choices, what is the expected number of questions answered before answering all questions correctly if answering a question incorrectly sends ...
5
votes
1answer
268 views

Recurrence for perfect matchings revisited.

I like to study combinatorics a bit as a hobby, and recently a question I found interesting was posed asking to derive a recurrence for the generating function $G_n(x)$, the ordinary generating ...
5
votes
2answers
66 views

Proving a solution to a double recurrence is exhaustive

The equation $$ b^2 = \frac{a(a+1)}{2} + 1 $$ where $a$ and $b$ are integers, has the following smallish-integer solutions: ...
5
votes
1answer
82 views

Expressing a recursively defined function in terms of factorials or gamma function

Given the recursion $$f(n) = nf(n-1) + (n-1)f(n-2) $$ $$f(0) = 1, f(1) = 1$$ How exactly does one express the target function? I know that $$f(n) = nf(n-1)$$ gives rise to $$f(n) = ...
5
votes
1answer
100 views

Recurrence for random walk

I have the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$. $p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < x$ $p_i = 1$ if ...
5
votes
3answers
206 views

How to solve this recurrence $T(n)=2T(n/2)+n/\log n$

How can I solve the recurrence relation $$T(n)=2T\left(\frac n2\right)+\frac{n}{\log n}$$? I am stuck up after few steps.. I arrive till $$T(n) = 2^k T(1) + \sum_{i=0}^{\log(n-1)} ...
5
votes
1answer
378 views

Deriving a recurrence relation

The number of sequences of length $n$ consisting of positive integers such that the opening and ending elements are $1$ or $2$ and the absolute difference between any $2$ consecutive elements is $0$ ...
5
votes
1answer
96 views

Geometric interpretation of the fundamental theorem for coalgebras?

Given an element $m$ in a coalgebra $C$, there always exists a finite-dimensional subcoalgebra $D \subset C$ containing $m$; this is the fundamental theorem for coalgebras. This obviously isn't the ...
5
votes
1answer
161 views

general technique to convert recurrence relation to integral

I know the following recurrence relation $$a_n=\frac{a+na_{n-1}}{a-n}$$ with $a_0=1$ can be represented alternatively as an integral $$a_n=a\int_0^1{x^{a-n-1}(2-x)^ndx}$$ Verifying this is easy, ...
5
votes
1answer
242 views

A nicer recurrence for the Eulerian polynomials.

I was perusing the subject of Eulerian polynomials. I'm assuming the definition that the Eulerian polynomial is defined by $C_n(t)=\sum_{\pi\in S_n}t^{1+d(\pi)}$, where $d(\pi)$ is the number of ...
5
votes
1answer
134 views

Solving a recurrence with diagonalization?

Considering the recurrence $F_n=F_{n-1}+3F_{n-2}-3F_{n-3}$ where $F_0=0$, $F_1=1$ and $F_2=2$. Use diagonalization to find a closed form expression for $F_n$. So I first continued the recurrence to ...
5
votes
1answer
48 views

Recursive identity for elliptic lattice constants $\sum_{\lambda\in\Lambda\setminus0} \lambda^{-2k}$

I am stuck on Exercise 3 in these notes. To keep this question self-contained: we have $\displaystyle\Lambda=\langle\omega_1,\omega_2\rangle=\omega_1\Bbb Z+\omega_2\Bbb Z\subset\Bbb C,$ ...
5
votes
4answers
103 views

Homework | Find the general solution to the recurrence relation

A question I have been stuck on for quite a while is the following Find the general solution to the recurrence relation $$a_n = ba_{n-1} - b^2a_{n-2}$$ Where $b \gt 0$ is a constant. I don't ...
5
votes
1answer
375 views

Purely combinatorial proof and simplification of identity involving factorials and summations

While trying to decompose factorials into summations, I came up with the following identity $$(n+2)! = 2^{n+1} + \sum\limits_{k=0}^{n-1}\sum\limits_{i=0}^{n-1-k}\sum\limits_{S \subseteq ...
5
votes
3answers
316 views

Find inverse for the closed-form expression of linear recurrence relation

I am trying to find an inverse of the following formula: $$ a_n=\frac{2+\sqrt{6}}{4}(1+\sqrt{6})^n+\frac{2-\sqrt{6}}{4}(1-\sqrt{6})^n $$ This formula is a closed-form expression of a linear ...
5
votes
1answer
78 views

Recurrence-differential equation

In his book on differential equations, Arnold writes that $x'(t)=x(x(t))$ is not a differential equation. My question is: how can one solve it?
5
votes
1answer
752 views

Recurrence relation for the integral, $ I_n=\int\frac{dx}{(1+x^2)^n} $

Express recurrence relation of the integral $$ I_n=\int\frac{dx}{(1+x^2)^n} $$ [My Answer] $$ I_n = \int\frac{1+x^2}{(1+x^2)^n}dx-\int\frac{x^2}{(1+x^2)^n}dx $$ $$ I_n=I_{n-1}-\int ...
5
votes
1answer
83 views

Does the A001921 linear recurrent integer sequence always yield composite numbers?

Let $(a_n)$ be the A001921 sequence $$ a_0 := 0,\ a_1 := 7, \quad a_{n+2} = 14a_{n+1} - a_n + 6. $$ Is it true that $a_n$ is always a composite integer for any $n\geq 2$ ? UPDATE : I now make a ...
5
votes
0answers
101 views

Sum of infinite series defined recursively

Suppose $s$, $t$, and $\delta$ are constants satisfying $0<s<t<1$ and $\delta>1$. An infinite sequence $\{y_k\}_{k=1}^{\infty}$ defined as follows: The initial term, $y_1$, is the ...
5
votes
0answers
40 views

Finding a recurrence relation for a sequence not containing $0$ in the digits. Also showing $\sum\limits_{k=1}^n \dfrac{1}{a_k} < 90$

Let $1,2,3,4,5,6,7,8,9,11,12,\ldots$ be the sequence of all positive integers which do not contain the digit zero. Write $\{a_n\}$ for this sequence. By comparing with a geometric series, show that ...
5
votes
0answers
67 views

Right way to solve this reccurence relation?

I am not that good in mathematics , I have solved many simple relations. But I am not be able to solve the following. This is not a homework. I found it during analysis of a program. ...
5
votes
0answers
164 views

General overview about Recursion (free online texts)

I'm looking for free online texts about recursion. What I'm looking for formal definitions* of "all" (most of) the different types of recursion and from different points of views like Category ...
5
votes
0answers
149 views

number of potential couples

A potential couple is a pair of a man and a woman that like each other (assume that 'like' is a symmetric relation). Given a group of $M$ men and $W$ women, I want to know how many different ...
4
votes
5answers
347 views

What is closed-form expression for $F(n)$ when $F(n)=F(n-1)+F(n-2)$ and $F(0)=a$,$F(1)=b$ and $a,b>0$?

What is closed-form expression for $F(n)$ when $F(n)=F(n-1)+F(n-2)$ and $F(0)=a$, $F(1)=b$ and $a,b>0$ ? It seems to be simple generalization of Fibonacci sequence but I can't find closed form for ...
4
votes
4answers
321 views

What's known about recurrences involving $(a_n)^2$?

I've run across the recurrence $a_{n+1} = (a_n)^2 + 1$ in the past. Unfortunately, the referrence escapes me. However, my impression was that recurrences involving the product of previous terms ...
4
votes
4answers
221 views

Recurrence relation $C_n = n + 1 + \dfrac{2}{n}\sum\limits_{k=0}^{n-1}C_k$.

A Discrete Mathematics book from which I'm self-studying ("Discrete Mathematics and Its Applications", by Kenneth Rosen) asks me to do the following: Given the following recurrence relation: $$C_n = ...
4
votes
4answers
263 views

Finding the billionth number in the series: $2, 3, 4, 6, 9, 13, 19, 28, 42, \ldots $?

Series is defined as $$a_{n+1} = \lfloor\frac{3\cdot a_n}{2}\rfloor,\qquad a_0 = 2$$ It can be viewed as the number of animals starting from a single pair if any pair of animals can produce a single ...
4
votes
2answers
125 views

Does this problem have a name?

Recently our lecturer told us that it is an unsolved mathematical problem if the following while loop aka iteration ever terminates. Unfortunately I forgot to ask him what it is called. If someone ...
4
votes
2answers
2k views

Fibonacci, tribonacci and other similar sequences

I know the sequence called the Fibonacci sequence; it's defined like: $\begin{align*} F_0&=0\\ F_1&=1\\ F_2&=F_0+F_1\\ &\vdots\\ Fn&=F_{n-1} + F_{n-2}\end{align*}$ And we ...
4
votes
4answers
288 views

Explicit formula for a recursion

How can you express the following recursion explicitly? \begin{cases} T_0 = 1\\ T_n = 1 + 2\cdot T_{n-1}\\ \end{cases}
4
votes
2answers
309 views

What is the closed form of this recurrence relation

I have the following recurrence relation : $$g(0) = c $$ $$g(i+1) = g(i) + (1-g(i))*g(i)^{2}$$ where 0 < c < 1. Is there any closed form for this relation? If not can you give me an upper ...
4
votes
5answers
389 views

Linear homogeneous difference equation with constant coefficients

If I have for instance the equation: $0 = 2x_{n} - 3x_{n+1}+x_{n+2}$ Then the solution space is a linear vector space of dimension 2. Someone who can explain why this is true? My teacher has ...
4
votes
4answers
437 views

How do I resolve a recurrence relation when the characteristic equation has fewer roots than terms?

I know how to solve "simple" recurrence relations. For instance, say you have: $$c_0 = 20$$ $$c_1 = 30$$ $$c_n = 3 c_{n-1} - 2 c_{n-2}$$ We can write the characteristic equation as: $$3x^{n-1} - ...
4
votes
3answers
1k views

Recurrence relation (linear, second-order, constant coefficients)

Q1. Find the general solution to the difference equation $$ a_{n} - 4a_{n-1} + 3a_{n-2} = 6 $$ Q2. Solve the difference equation $$ a_{n} - a_{n-1} - 2a_{n-2} = 0, a_0 = 2, a_1 = 4 $$ I am ...
4
votes
3answers
2k views

Recurrence trouble: $T(n)=2T(n/2)+T(n/3)+\theta(n^2)$

I have to solve the following recurrence :$\displaystyle T(n)=2T(n/2)+T(n/3)+\theta(n^2)$ I have done the whole tree analyses and now I have to prove that $\displaystyle T(n) \leq ...
4
votes
2answers
274 views

Sum of the series formula

I need to figure out the sum of the series as quickly as possible in a program given n and k: $$f(n,k)= ...
4
votes
3answers
2k views

Solving $T(n)= 2T(n/2)+n \lg (n)$

I am trying to solve a recursive function: $$ T(n)= 2 T(n/2)+n \lg(n), \quad n>2,\quad T(2)=2,\quad n = 2^{k}$$ Master theorem didn't work. The result is pointless (if I did it right). Any ...
4
votes
1answer
377 views

$a_n=20a_{n-1}+12a_{n-2}$ recurrence relation question

Respected Sir, Please solve the below problem. Please... Consider the infinite $\displaystyle\mathbb{S}=\sum_{n=0}^{\infty}\frac{a_n}{10^{2n}}$, where the sequence $\{a_n\}$ is defined by ...
4
votes
3answers
258 views

What is the most elementary way of proving a sequence is free of non-trivial squares?

Given the sequence A001921 $$ 0, 7, 104, 1455, 20272, 282359, 3932760, 54776287, 762935264, 10626317415, 148005508552, 2061450802319, 28712305723920, 399910829332567, \dots $$ which obeys the ...
4
votes
3answers
165 views

How does $\tbinom{4n}{2n}$ relate to $\tbinom{2n}{n}$?

I got this question in my mind when I was working on a solution to factorial recurrence and came up with this recurrence relation: $$(2n)!=\binom{2n}{n}(n!)^2$$ which made me wonder: is there also a ...
4
votes
3answers
239 views

Combinatorial Proof for a Recursive Sequence

For $n>3$ let $g_n = g_{n-1} + g_{n-3}$ where the recursion takes the value 1 for n = 0,1,2. Prove that $g_{2n} = (g_n)^2 + 2g_{n-2}g_{n-1}$ combinatorially, $n > 1$. For the time being I am ...
4
votes
4answers
395 views

How to solve this recurrence relation?

There's a frog who could climb either 1 stair or 3 stairs in one shot. In how many ways he could reach at 100th stair? I came up with the solution $g(n) = g(n-3) + g(n-1)$, where $g(0)=g(1)=g(2)=1$ ...
4
votes
3answers
103 views

To show sequence $a_{n+1}= \frac{a_n^2+1}{2 (a_n+1)}$ is convergent

Let $a_1=0$ and $$a_{n+1}= \dfrac{a_n^2+1}{2 (a_n+1)}$$ $\forall n> 1.$ Show that sequence $a_n$ convergent. I tried to prove $a_n$ is less than 1 by looking at few terms. But i failed to prove ...
4
votes
3answers
149 views

Need help about solving a recurrence relation

I have a recurrence relation which is like the following: $$ T(n) = 2T(n/2) + \log_2 n. $$ I am using recursion tree method to solve this. And at the end, i came up with the following equation: $$ ...
4
votes
3answers
214 views

Maximum based recursive function definition

Does a function other than 0 that satisfies the following definition exist? $$ f(x) = \max_{0<\xi<x}\left\{ \xi\;f(x-\xi) \right\} $$ If so can it be expressed using elementary functions?
4
votes
4answers
161 views

What sort of math is this, and how would I solve it?

I'm taking a computer science class after several years away from school and so far I'm doing all right. However, we're covering some math and I'm drawing a blank on what to even call this concept, ...
4
votes
2answers
172 views

Solving a recurrence using substitutions

I have to solve this recurrence using substitutions: $(n+1)(n-2)a_n=n(n^2-n-1)a_{n-1}-(n-1)^3a_{n-2}$ with $a_2=a_3=1$. The only useful substitution that I see is $b_n=(n+1)a_n$, but I don't know ...
4
votes
1answer
113 views

Going from closed form to recurrence relation

If I had a closed form for a sequence that I suspect to represents a recurrence relation how would I determine the recurrence relation? In particular, I have the sequence $$a_n = ...