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

learn more… | top users | synonyms

1
vote
2answers
34 views

First order recurrence relation

I have to solve this relation: $$a_1 = k \\ a_n = \frac{10}{9} a_{n-1} + k + 1 - n$$ (k is constant) How can I do it??
1
vote
1answer
31 views

How to convert linear recurrence to a tiling question

If I have some linear recurrence of form $$f(n) = a_1f(n-1) + a_2f(n-2) + a_3f(n-3) + \cdots + a_kf(n-k)$$ How does this translate to tilings? For example the Fibonacci sequence is the same as ...
0
votes
1answer
61 views

Solve the recurrence relation $f(n) = f(n - 1) + f(n - 2) + f(n - 3)$

This is a problem I was playing with that troubled me greatly. $f(n) = f(n - 1) + f(n - 2) + f(n - 3)$ $f(1) = f(2) = 1$ $f(3) = 2$ So, the goal is to try and find a solution for f(n). I tried ...
1
vote
1answer
35 views

Help with recurrence equation

I need to solve the following recurrence equation $p_i =\begin{cases} r(p_{i-1}+p_{i+2}) &\mbox{if } i \text{ is odd} \\ (1-r)(p_{i-1}+p_{i}) & \mbox{if } i \text{ is even} \end{cases} i ...
0
votes
0answers
37 views

Solution to the recurrence relation with two equations

I am given : $$\begin{cases} v(0) = 0 \\ v(n)=\frac{1}{3}v(n+1)+\frac{2}{3}v(n-1)+1 & \text{ for } n < m\\ v(n)=k+v(1) & \text{ for } n \ge m\\ \end{cases}$$ The general solution to ...
6
votes
3answers
87 views

Please solve this recurrence relation question for $8a_na_{n+1}-16a_{n+1}+2a_n+5=0$

Suppose $a_1=1$ and $$8a_na_{n+1}-16a_{n+1}+2a_n+5=0,\forall n\geq1,$$Please help to sort out the general form of $a_n$. Here are the first a few values of the series. Not sure if they are useful as ...
4
votes
4answers
273 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}
0
votes
1answer
20 views

Geometric recurrence, prove $g(k)=3g(k-1)-2g(k-2) is g(n)=2^n+1$

Geometric recurrence, prove gk = 3g(k-1) - 2g(k-2) is gn = 2n+1 using iteration. g1 = 3, g2 = 5 So, g3 = 3g(2) - 2g(1) = 3(5) - 2(3) = 9 <---- *which is 23+1 = 8+1 = 9 I'm unsure how to ...
0
votes
2answers
79 views

Integral of $\sin^n(x)$, recurrence relation, some properties

Practicing the manipulation of recurrence relations, I'm stuck on this : Defining $I(n)=\int_{0}^{\pi/2}sin^n(x)dx$, I got the recurrence relation $nI(n)=(n-1)I(n-2)$ for $n\ge2$. Now I'm also ...
1
vote
2answers
23 views

Not sure how to do Non-Homogeneous Recurrence Relations

I have a sample exam paper, and the answer is given, but I can't work out the answer from the question: Find the solution of: $a_n = \frac{1}{3}a_{n-1} + 2$ using $a_0 = 4$ Given Answer: $a_n = ...
1
vote
0answers
30 views

Solving a recurence system

Find a function $f(x,y) : \mathbb{N}^2 \to \mathbb{N}^2$ such that: $1 + f(x+1,y) - f(x,y) = a$ $1 + f(x, y+1) - f(x,y) = b$ $k + f(x-k, y) - f(x,y) = c \space \forall k \leq x$ $k + f(x,y-k) - ...
3
votes
1answer
50 views

2D Pattern in recursive digit sum of consecutive x^n

Take the recursive decimal digit sum of consecutive binary numbers $2^n$ as $n \to \infty$. You'll see something like this: n 2^n (recursive) sum of digits ...
0
votes
1answer
30 views

Solving Recurrence Relation Question

How do i solve recurrence relations like $a(n) = 3a(n/2) - 2a(n/4); a(1)=3; a(2)=5$? I don't think I can draw a recursion tree since there's no function like $2n$ at the end.
-1
votes
1answer
24 views

Understanding non homogeneous recurrence

Find a particular and then the general solution for the recurrence relation $a_n = 7\cdot a_{n−1} − 30 \cdot 2^n$ Trying to understand this equation.... We have been given a general formula for this ...
1
vote
3answers
46 views

Understanding a recurrence relation question.

A computer system considers a bit string a valid codeword if and only if it does not contain $3$ consecutive zeroes. Thus $010010$ is a valid codeword of length $6$ while $011000$ is not. Let $a_n$ be ...
0
votes
0answers
26 views

Second order, constant coefficient, homogeneous, linear difference equation

$a_n=x^2-5x+6=0$ So $x$ = $2$, $3$ Theorem $a_n=k_1 \alpha^n +k_2\beta^n $ Choice [1], I choose $2$ to be $\alpha$ and $3$ to be $\beta$ Then I get $a_n=A_1 2^n+A_23^n$ Choice [2], I choose $3$ to ...
1
vote
2answers
39 views

Recurrence with multiplication

Let $\{a_{n}\}$ be a sequence of nonnegative numbers such that $a_{n} = 2^{n}a_{n - 1}^{3/2}$. If $a_{1}$ is sufficiently small, why must $a_{n} \rightarrow 0$ as $n \rightarrow \infty$?
0
votes
1answer
45 views

How often does $p^k$ divide the Fibonacci numbers?

I would like to know about the Fibonacci numbers $F_n = 1,1,2,3,5,8, \dots$ in $\mathbb{Z}/p^k\mathbb{Z}$. $$ \mathbb{P}[p^k \text{ divides } F_n ] = \frac{\#\{1 \leq n\leq N: F_n \equiv 0 \mod ...
-2
votes
1answer
38 views

N balls of k colors on a cirlce, no two neighboring balls have same color - recursive algorithm

Suppose we have N balls of k different colors. What is the number of arrangements of these N balls on a circle with no two neighboring balls having the same color? Actually, the task is to make up a ...
2
votes
1answer
44 views

Recursive formula for creating a specific string

I have 5 characters ${a,b,c,1,2}$. $a_n$ is the number of strings I can create for $n$ length. I can't have the following sequences in a string: $a1$, $b2$ and any sequence of numbers $(12, 21)$. For ...
2
votes
3answers
32 views

Recursive integration

The integral I have is $$I_{n} = \int^{\pi/2}_{0} \cos^{2n+1}y \ \mathrm{d}y$$ And I have found $I_{n} = \frac{2n}{1+2n}I_{n-1}$ but I want to express $I_{n}$ in a form without $I_{n-1}$ how do I do ...
0
votes
2answers
43 views

Closed form for a strong recurrence relation

Let $\alpha_n$ be a sequence of complex numbers and consider the sequence $b_n$ defined by the (strong) recurrence relation : $$b_{n+1} = \sum_{k=0}^n \alpha_{n-k} b_k$$ with the initial condition ...
1
vote
1answer
37 views

Solving a (non-linear?) recurrence relation in 2 variables

I'm not sure if this problem is linear or not. Anyway, let me state the problem first: $$ \begin{align} P_n(a) &= \left(1 - \frac{a}{n} \times \frac{a-1}{n-1}\right) \times P_{n-1}(a) + ...
4
votes
4answers
243 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 ...
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
28 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
57 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
64 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
87 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
129 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 ...