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

learn more… | top users | synonyms (2)

5
votes
1answer
93 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
160 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
240 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
124 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
46 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
100 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
371 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
314 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
76 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
691 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
81 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
93 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
38 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
64 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
141 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 ...
5
votes
0answers
539 views

The Average Running Time Of Euclid Algorithm?

What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$? It seems very hard to deduce from the recurrence $T(m,n) = T(n, m ...
4
votes
5answers
330 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
320 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
218 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
261 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
124 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
1k 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
282 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
306 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
423 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
271 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
374 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
249 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
163 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
232 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
366 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
143 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
212 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
1answer
110 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 = ...
4
votes
1answer
65 views

Non-linear Recurrence relation

I am concerned to solve the recurrence relation $T(n)=nT^2\left(\frac{n}{2}\right)$ with initial condition T(1)=6. I have tried to do some transformation like $N=2^k$ and some other things like that ...
4
votes
2answers
1k views

Inductive proof of the closed formula for the Fibonacci sequence [duplicate]

Fibonacci numbers $f(n)$ are defined recursively: $f(n) = f(n-1) +f(n-2)$ for $n > 2$ and $f(1) = 1$, $f(2) = 1$. They also admit a simple closed form: $$\sqrt 5 f( n ) = \left(\dfrac{1+ \sqrt ...
4
votes
3answers
71 views

Solving a set of recurrence relation:

Solving a set of recurrence relation: $a_n=3b_{n-1} , b_n=a_{n-1}-2b_{n-1}$ In addition, It's known that: $a_1=2, b_1=1$. So i started by isolating $b_n \to b_n=3b_{n-2}-2b_{n-1}$ So i get the ...
4
votes
2answers
145 views

Combinatorial solution to a recurrence problem

I found today this problem in some old blog post: Suppose that $a_n$ is a sequence of positive integers such that $$ \sum_{d |n} a_d =2^n$$ for every positive integer $n$. Prove that $ n | a_n$. It ...
4
votes
4answers
159 views

Expansion of $x^4\over1+x^2$ into a power series

I calculated the generating function $A(x)$ of the recurrence $a_n = a_{n-2} - 2a_{n-3}$, $(n \ge 0, a_0 = a_1 = 0, a_2 = 2)$ and I have no clue on how to expand it into a power series in order to ...
4
votes
2answers
325 views

Understanding why the roots of homogeneous difference equation must be eigenvalues

There is some obvious relationship between the root solutions to a homogeneous difference equation (as a recurrence relation) and eigenvalues which I'm trying to see. I have read over the wiki article ...
4
votes
2answers
6k views

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

How can I solve the recurrence relation $T(n) = 2T(n/2) + n\log n$? It almost matches the Master Theorem except for the $n\log n$ part.
4
votes
2answers
146 views

A mouse leaping along the square tile

A $n \times n$ square is made of square tiles of dimensions $1\times1$. A mouse can leap along the diagonal or along the side of square tiles. In how many ways can the mouse reach the right lower ...
4
votes
2answers
689 views

How to approach 2-Dimensional Recurrence Relations

How to solve the following 2-dimensional recurrence relation? Let $n, n'$ be natural numbers $> 0.$ Let $r$ be a positive integer $\ge 0.$ $$ P(n+n',r) = \sum_{i=0}^{r} P(n, ...
4
votes
2answers
327 views

Recurrence for $q$-analog for the Stirling numbers?

I read in some papers that the Stirling numbers (of the second kind) have a natural $q$-analog $S_q(n,k)$, which satisfy the recurrence $$ S_q(n,k)=(k)_qS_q(n-1,k)+q^{k-1}S_q(n-1,k-1) $$ with the ...
4
votes
2answers
169 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 ...