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

learn more… | top users | synonyms

0
votes
0answers
26 views

Convergence rate of $x_{k+1}=3x_k^2/n+3$

I've found the following claim in a slightly different form here (page 4, bottom of the left column) Starting from $x_0\le n/3$, the recurrence equation $$3\le ...
1
vote
0answers
29 views

Analytic Function Derived From Recursive Reverse Taylor Series?

Given the following recursive relation: $a_0 = 1,$ $a_n = a_{n-1}(p-2q)+2(-p)^n$ is there a simple function that has this as its Taylor series, i.e. $f(x) = \sum_{n=0}^{\infty} \frac{a_n}{n!}x^n$ ...
0
votes
1answer
32 views

generating functions for $S(n,3)$

I would like to find a closed formula for the Stirling numbers of the second kind $S(n,3)$ or the number of ways to partition a set of 3 elements into 3 sets. I know that $S(n,3)=3S(n-1,3)+S(n-1,2)$ ...
1
vote
1answer
48 views

Solve $X_n=\lfloor \sqrt{X_n} \rfloor+X_{n-1}$

How do I solve $X_n=\lfloor \sqrt{X_n} \rfloor+X_{n-1}$? The initial terms are $1,2,3,5,7,10,13,17,21,26,31$. A search on oeis.org/ gave $\lfloor n/2 \rfloor\cdot\lceil n/2 \rceil$ + 1 which should be ...
0
votes
0answers
19 views

What is the asymptotic bound of the recurrence : $T(n)= 2T\frac{n}{2}+\log n$?

I have managed to reach upto : $T(n) = 2.n.\log n - \log n - [2+2.2^2 +3.2^3 + \dots\log_2 n.2^{\log_2 n}]$ I m stuck here and not getting any clue how for solving the arithmetico-geometric series. ...
1
vote
5answers
108 views

A non-homogenous linear recurrence: Why does my method fail?

I'm trying to solve this recurrence relation: $$a_m = 8 \cdot a_{m-1} + 10^{m-1}, a_1=1$$ By the change of variable $\displaystyle b_m = \frac{a_m}{10^m}$ I obtained this linear non-homogenous ...
2
votes
2answers
72 views

Zeroes of polynomial

$$c_1,c_2 \text{ are polynomial's }g(x)=x^2+ax+b \text{ roots } \Leftrightarrow \begin{cases} g(c_1)=c_1^2+ac_1+b=0 \\ g(c_2)=c_2^2+ac_2+b=0 \end{cases}$$ Prove that for every polynomial with integer ...
2
votes
2answers
32 views

Find general solution

I want to find the general solution for the following : $$t(n)=t(\frac{n}{4})+\sqrt{n}+n^2+n^2log_{8}n $$ Note: $n=4^k$ $t(n)=t(4^k)=t_{k}$ $$t_{k}=t_{k-1}+2^k+16^k\cdot \frac{2}{3}k$$ ...
13
votes
3answers
193 views

For $x_{n+1}=x_n^2-2$, show $\lim_{n\to\infty}\frac{x_n}{x_0x_1\cdots x_{n-1}}=2$

Suppose $x_0:=2\sqrt{2}$ and $x_{n+1}=x_n^2-2$ for $n\ge1$. We have to show $$\lim_{n\to\infty}\frac{x_n}{x_0x_1\cdots x_{n-1}}=2$$ Establishing convergence is pretty direct but I'm having trouble ...
0
votes
1answer
58 views

Recursive Function - $f(n)=f(an)+f(bn)+n$

I've got this recursive function $f(n)=f(an)+f(bn)+n$, and I need to find $θ$ on $f(n)$, as $a+b>1$. Using a recursive tree, I managed to bound it by $n\log(n)$ from the bottom and by $n^2$ from ...
2
votes
2answers
23 views

Solving divide and conquer recurrence

I have a recurrence $T(n)$ with only powers of two being valid as values for $n$. $$T(1) = 1$$ $$T(n) = n^2 + \frac{n}{2} - 1 + T(\frac{n}{2})$$ I tried to substitute $n=2^m$, which yields the ...
1
vote
1answer
36 views

Recurrence Relation all general solutions

I need some help solving the following recurrence relation: $a_n = 4a_{n-1} - 4a_{n-2} + (n+1)*2^n$ What I've tried: a) Find the general solution of the associated linear homogenous recurrence ...
0
votes
0answers
26 views

Solve the following recurrence relation : $t(n)=11t(\frac{n}{2})+n^6 \cdot \log_{11}n$ and $n=2^k$ , $k \geq 1$

I want to solve the following: $$t(n)=11t(\frac{n}{2})+n^6 \cdot \log_{11}n$$ Note : $n=2^k$ , $k \geq 1$ what I did so far is: $$t(n)=t(2^k)=t_k$$ $$t(\frac{n}{2})=t(2^{k-1})=t_{k-1}$$ ...
0
votes
0answers
16 views

Can someone help me solve this recurrence using the Master Theorem?

Can someone help me solve this recurrence? $$T(n)= T(n^{1/2}) + Θ(\log\log n)$$ I know that I have to change the variables $m=\log n$. Then I have: $$S(m)=S(m/2)+Θ(\log m)$$ Case 2 of Master ...
1
vote
1answer
66 views

Solving recurrence relation: f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3

f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3 I have attempted to solve it by letting n = 2k f(2k) = 3f(2k-1) - 2f(2k-2) Then set S(k) = f(2k) S(k) = 3*S(k-1) - 2*S(k-2) ...
2
votes
3answers
150 views

Fibonacci polynomials and factorization redux

I recently asked a question about factorizing a certain expression involving Fibonacci and Lucas polynomials. That question had a very simple and nice answer, but now I've come across another similar ...
1
vote
1answer
16 views

third order recurrence relation with non-constant coefficients

Does anyone know of a paper that may have been written on $3^{rd}$ order recurrence relations with polynomial coefficients, that is, one of the form $$A(n)a_{n+3}+B(n)a_{n+2}+C(n)a_{n+1}=D(n)a_n$$ ...
1
vote
2answers
90 views

Find an explicit formula for the recursive sequence (tips?)

Problem: A sequence is defined recursively as follows: Sk = 2k - Sk - 1, for all integers k greater than or equal to 1 S0 = 1 Use iteration to guess the explicit formula for the sequence. Use ...
1
vote
3answers
30 views

Given initial conditions and a recurrence relation, what is closed form in terms of n?

We are given that $a_0$ = 1000, and $a_1$ = 3000, and that $\forall n \geq 2$, $a_n = \frac{a_{n-1} + a_{n-2}}{2}$. What is the value when $n$? I've determined that, in the long run, it converges to ...
5
votes
3answers
130 views

The number of length-n ternary sequences with even ones and even zeroes

Just starting to appreciate recurrence relations Let $T_n = $ number of length-n ternary sequences with an even number of ones and an even number of zeroes. $T_0 = 1$, because $0$ is an even number, ...
0
votes
1answer
30 views

Why does $T(n) \leq 2 T(\lceil \frac{n}{2} \rceil)+\mathcal{O}(n)$ imply $T(n)=\mathcal{O} (n\log(n))$

I am learning about sort algorithms and their complexities. For merge sort, I'm confronted with $T(n) \leq 2 T(\lceil \frac{n}{2} \rceil)+\mathcal{O}(n)$. The author makes the claim with no ...
4
votes
1answer
94 views

Is there a generating function for $\sqrt{n}$?

I tried to come up with a closed form for the ordinary generating function for the sequence $\{\sqrt{n}\}_0^{\infty}$ but I could not. Is there a way to derive it using the recurrence relation ...
0
votes
0answers
22 views

Inhomogenous Recurrence Relation: Looks correct?

I'm working on the problem below currently. I feel that I am doing everything correctly, but I just have this tiny problem that's causing me issues! I've attached my working out below. As ...
3
votes
4answers
192 views

Solving Recurrence equation

I have a problem with this type of recurrence equation. Find the solution of recurrence equation: $$T(1)=2,$$ $$T(n+1)=T(n)+2n , \quad \forall n\geq 1$$ Indeed, I tired to Solving Recurrences ...
1
vote
2answers
75 views

How many $a$-nary sequences of length $b$ never have $c$ consecutive occurrences of a digit?

Let $S(a,b,c): = \#\{a$-nary sequences of length $b$ without $c$ consecutive occurrences of a digit$\}$. For example, $S(2,n,3)$ would be the number of binary sequences of length $n$ without $3$ ...
0
votes
1answer
25 views

math notation of iterated function

I'm trying to determine the proper notation for the following loop I have written in computer code: Set x = 2 set y = 3 For z=1 to z=5 (increasing the value of z by 1 each ...
1
vote
1answer
97 views

Number of n-digit ternary sequences with an even number of 0's and 1's

Can someone help me derive a recurrence relation to find the number of n-digit ternary sequences with an even number of 0's and 1's? I know that you need to break it down into cases where the ...
2
votes
1answer
54 views

Number of ways to derive the number 14 using a recursive definition of EVEN numbers?

I have the following recursive definition for the construction of EVEN Numbers- [RULE 1]: 2 is an EVEN number. [RULE 2]: If x is an EVEN number and y is an EVEN number, then x+y is also an EVEN ...
2
votes
2answers
103 views

Non homogeneous Recurrence relation problem

So here i have this non homogeneous recurrence relation i need to solve: $$a_{n}=12a_{n-2}+16a_{n-3}+9\cdot 4^{n}+81n,$$ where $a_{0}=0$, $a_{1}=1$ $a_{2}=98$. I'm confused at the homogeneous ...
5
votes
0answers
35 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 ...
0
votes
2answers
23 views

Is it a solution of the recurrence relation?

I am given a recurrence relation such that $a_n = 2a_{n-1} - a_{n-2}$ for $n = 2, 3, 4...$ I am to test whether $a_n = 2^n$ is a solution to the recurrence relation. I am new to this, but it seems ...
1
vote
1answer
73 views

Need help with recurrence relation

So the question is: "Find a recurrence relation for the number of ways to pick $n$ objects from $k$ types with at most 3 of any one type" I think I figured out what it would be excluding the last ...
0
votes
1answer
119 views

find the recurrence relation (homework)

I'm new to recurrence relations and I'm having trouble figuring out this problem: Find a recurrence relation for the number of ways to make a stack of green, yellow, and orange napkins so that no two ...
0
votes
1answer
23 views

Going from recurrence relations to closed form

How do I go from the following recurrence relation a(n) = (n+1)a(n-1) where a(0) = 2 to a closed form? I know I need to use an iterative approach but I am not ...
1
vote
0answers
36 views

Infinitely many primes in second-order recurrence

I just wondered about the following question: Suppose that we are given a homogeneous second-order recurrence relation, $x_{n+2}+ax_{n+1}+bx_n=0$ for all $n\in\mathbb{N}$. Can we choose integers ...
3
votes
2answers
91 views

Proving integrality of a sequence of numbers

How would one go about proving whether or not the terms of a sequence such as the following $$1, 1, 1, 1, 1, 6, 21, 181, 5221, 1090981, 986241401, 51490676208426,\ldots$$ defined by ...
3
votes
1answer
76 views

UNBEATABLE recurrence relation

Hi I don't know where to start to solve this reccurence relation: $g(1)=2$ $ g(2n)=3g(n)+1$ $ g(2n+1)=3g(n)-2$ of coures I can make it: $ g(1)=2$ $ g(n)=g(2n)/3-1/3$ $ ...
1
vote
1answer
37 views

Solve the following recursive relation by using generating functions

$a_n - 9a_{n-1} + 26a_{n-2} - 24a_{n-3} = 0, n \ge 3, a_0 = 0, a_1 = 1,a_2 = 10$ I have tried solving it by the normal way, but I have no idea how to solve it by generating functions. Please give me ...
1
vote
2answers
60 views

Find the generating function?

How can I find a generating function for the following mathematical term? $$ a_r = \left(\matrix{2r \\ r}\right) $$ Is it the $\dfrac{r!}{2r(2r-r)!} = \dfrac{(2r-1)\cdot(2r-2)\cdot\ldots\cdot ...
1
vote
2answers
38 views

How can I find a recursive relation for the following words?

if $d(n)$ is the number of words created by the alphabet $\{a,b,c\}$ of length $n$ that do not contain $abc$ term then write a recursive relation for $d(n)$. I have read the same questions but there ...
2
votes
1answer
39 views

How can I find a recursive relation for the following words?

if c(n) is the number of words created by the alphabet {a,b,c} with n length that the word does not contain 'ab' term then write a recursive relation for c(n). I don't have enough knowledge of the ...
2
votes
2answers
35 views

Find suitable recurrence relation

So I need to find a correct recurrence relation to this problem: How many series of size n over {0,1,2} exist, so that each digit never appears alone. For example, this series is good: 000110022, and ...
1
vote
1answer
33 views

set problem of integers

Consider the following set $F=\{F^0, F^1, F^2, \ldots\}$. This set consists of positive integers which satisfy the following properties: $F^0= F^1=1$ AND $F^n= F^{n-1} + F^{n-2}$ for all positive ...
0
votes
0answers
16 views

recursive relation in rational expression form

I am looking for a closed form expression for the variables $n_i$ that are stationary solutions of the recursive relation: $ n_i(t+1)=n_i(t)\sum_mf_{i,m}\frac{K_m}{\sum_j f_{j,m}n_j(t)}$ i.e. the ...
0
votes
1answer
27 views

Relation between coefficients of Maclaurin series and recurrence relations

Suppose $I_{2n}=\int_0^{\pi}x\sin^{2n}x \;dx$. Then one can obtain the following: $$I_0= \frac{\pi ^2}{2}, I_1= \frac{\pi ^2}{4}, I_2= \frac{3\pi ^2}{16}, I_3= \frac{5\pi ^2}{32},\ldots, I_n= ...
0
votes
2answers
46 views

Recurrence for number of strings of length n without consecutive vowels

Someone asked almost the same question recently, but I'm having a ton of trouble trying to calculate the rest of the problem.
1
vote
2answers
66 views

How can I get the following recursive relation that explained?

if $b(n)$ is the number of words created by the alphabet ${a,b,c}$ with $n$ length that each word has at least one $a$ character and after each $a$ there is no $c$ character write a recursive relation ...
0
votes
1answer
32 views

How can I get the following recursive relation? [closed]

if $a(n)$ is the number of words created with the alphabet $\{a,b\}$ and with $n$ length and with no $aaa$ term then write a recursive relation for $a(n)$.
7
votes
1answer
302 views

How to prove this sequence of inequalities

The number $c_{g}(n)$ is defined by the recurrence \begin{equation} c_{g}(n) = c_{g}(n-1)+ (n-1)(n-2)c_{g-1}(n-2) , \end{equation} with $c_{0}(n)=1$ for any $n\geq 1$ and $c_{g}(n)=0$ if $n \leq 2g$. ...
0
votes
2answers
28 views

Find $f(n)$ when $n = 2^k$ where $f$ satisfies the recurrence relation $f(n) = f\left(\frac{n}{2}\right) + 1$ with $f(1) = 1$

Given: $f(1) = 1$. Answer: $$f(2) = f(1) + 1 = 1 + 1$$ $$\ldots$$ $$f(4) = f(2) + 1 = 1 + 1 + 1.$$ How do I find the value of $f(n)$ where $n$ is an odd integer? Let say $f(3) = ...