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

learn more… | top users | synonyms (2)

0
votes
1answer
23 views

Polynomials: functions of functions integer roots

I'm attempting to prove: Define functions $f_m$ by the recursion relation such that $f_1(x) = 2x^2-1$ and $f_k(x) = f_1(f_{k-1}(x))$ . Then for all $ m > 0$, there exists no $x \in \mathbb Z$ ...
3
votes
0answers
42 views

Relation between 2 recurrence equations.

I am stuck with the following recurrence relations (actually asked in a programming question).Given the following relationships, is it possible to find the index of the occurrence of any given number ...
0
votes
1answer
13 views

Solving second order difference equations with non-constant coefficients

For the difference equation $$ 2ny_{n+2}+(n^2+1)y_{n+1}-(n+1)^2y_n=0 $$ find one particular solution by guesswork and use reduction of order to deduce the general solution. So I'm happy with ...
0
votes
1answer
30 views

How to find a recursive formula for some sequence

I know how to find a non-recursive formula for a recursively defined sequence. However, now I have this puzzle which gives me a sequence (but not the recursive definition) and challenges me to find ...
0
votes
1answer
26 views

Creating equation for a given recurrence relation

I'm studying discrete math in the university, and we are given questions and answers for some problems, and I dont understand most of them. So I need help understanding one of them... Appreciate the ...
1
vote
1answer
10 views

Looking for a recurrence relation ot combinatorial way to calculate initial number

A flock of birds migrating south flies above seven lakes. Half of the birds in the flock, plus half a bird(I'm guessing the initial flock contained an odd number of birds, say 5, so in the first lake ...
0
votes
2answers
35 views

Solve the recurrence relation (using iteration?)

$a_n = a_{n-1} + 1 + 2^{n-1}\\ a_0 = 0$ Not sure how to iterate with the exponent term. Here's what I got: $= (a_{n-2} + 1 + 2^{n-1}) + 1 + 2^{n-1} = a_{n-2} + 2 + 2(2^{n-1})\\ = (a_{n-3} + 1 + ...
3
votes
2answers
36 views

How to solve linear, second order ODE with Frobenius method with a difficult recurrence relation?

The ODE in question is: $$4xy''+2y'+y=0$$ Shifting the power series of each term so that they are all raised to the power $(n+r)$ will yield this recurrence relation: $$a_{n+1}={a_n\over ...
2
votes
1answer
39 views

Understanding Generating Function

I have been looking at This Problem and Answer about generating functions. The problem asked for the generating function of: $$a_n=4a_{n-1}-4a_{n-2}+{n\choose 2}2^n+1$$ I understand how Ron Gordon ...
0
votes
1answer
24 views

Recurrence relation advice

$t_n=5t_{n-1}+6t_{n-2}$ Is the characteristic equation of this correct? This is what I have: $x$- 5$x$ -6=0 Is this correct?
1
vote
3answers
33 views

Finding a closed-form formula for a sequence that is defined recursively

$$a_0 = 0, a_1 = 1 \quad \text{ and } \quad a_n = a_{n-1} + 2a_{n-2}\quad \text{ for }n\geq 2$$ a) Find $a_2,a_3,a_4,a_5$ b) Find a closed form-formula for $a_n$ I found the value to be ...
2
votes
1answer
73 views

Solve the recurrence relation: $2a_n = 7a_{n-1} - 3a_{n-2}; a_0 = a_1 = 1$

$2a_n = 7a_{n-1} - 3a_{n-2}\\ a_0 = a_1 = 1$ My attempt: $2t^2 - 7t + 3 = 0\\ t = -\frac{1}{2}, -3\\ \\ U_n = b(-\frac{1}{2})^n + d(-3)^n\\ b+d = 1 = -\frac{1}{2}b-3d\\ b = \frac{8}{5}, d = ...
0
votes
1answer
36 views

Solve the Recurrence

Solve the recurrence $a_k = 2a_{k-1} + 3a_{k-2}$, if $a_0 = 0$ and $a_1 = 8$. I understand how to get the generating function: $$G(x) = \sum_{k \geq0}a_kx^k = a_0 + a_1x + \sum_{k\geq 0}a_kx^k = 8x ...
1
vote
2answers
49 views

Solve the recurrence $a_{n+2}=5a_{n+1}-9a_n+3n$?

What is the simplest way to solve the recurrence $a_{n+2}=5a_{n+1}-9a_n+3n$, with the initial values $a_0=2,a_1=1$? Is it possible to do this with generating functions?
1
vote
1answer
26 views

Recurrence relation stuck on partial fraction decomposition

I am stuck in trying to solve the following recurrence relation: $$S_n = rS_{n-1} + nrB$$ where $r$ and $B$ are constants. To solve this I made the following generating function: $$f(x) = ...
1
vote
0answers
10 views

Asymptotic Notations Iterative Method for Solving Recurrences

Recurrence T(n)= T(n^1\2) + O(lg(lg(n))) The solution suggests substituting m = lg(n) So the recurrence becomes S(m)= S(m\2) + O(lg(lg(m))) Then solving using iterative method for solvng ...
0
votes
1answer
19 views

Part of a proof recurrence relation

I'm reading this survey by Carl Offner about digit computation of the number $\pi$. In page 7 there's a step that I didn't understand: suppose $$\alpha_{n+1}=\frac{\alpha_n \beta_n}{\alpha_n + ...
0
votes
2answers
11 views

Solving a single-term recurrence relation with a variable coefficient?

$a_n = 2na_{n-1}\\ a_0 = 1$ How do I solve this? Is there a characteristic equation? I found $a_1 = 2, a_2 = 8, a_3 = 48$ but I don't know what to do with that information to solve. Please help, ...
0
votes
0answers
15 views

Solving single term recurrence relation?

$a_n = -3a_{n-1}\\ a_0 = 2$ Therefore $a_1 = -3(2) = -6\\ a_2 = -3(-6) = 18\\ a_3 = -3(18) = 54$ So... $x^n = -3^{n-1}$? If so $x^2 = -3^1$, so $x^2 + 3 = 0$, then $x = \pm (i\sqrt3)$. That doesn't ...
1
vote
2answers
38 views

two recursive sequences and the limit of their quotient

The sequences $\left \{ a_{n} \right \}$ and $\left \{ b_{n} \right \}$ are defined by the following recurrence relations: $a_{1}=b_{1}=1$ $a_{n+1}=a_{n}+2b_{n}$ $b_{n+1}=a_{n}+b_{n}$ What ...
0
votes
1answer
29 views

Simple question about recursive sequence format regarding $a(n+2) = -4a(n+1) + 5a(n)$

Suppose there's a recursive sequence $a(n+2) = -4a(n+1) + 5a(n)$ How can i convert it into the form $a(n)$ because I am most comfortable solving questions in this form. I tried to find out but I'm ...
1
vote
1answer
58 views

How to approach an equation of the form $f(x)=y$ where $f$ is recursively defined? [duplicate]

This is a homework problem so I am not looking for someone to solve it for me. I would like to know how I should approach this problem, or in what direction I should research to figure it out myself. ...
0
votes
1answer
22 views

Recurrence relation of distances between $n$-dimensional curves

I have a problem involving recurrence and euclidean distances in $n$-dimensional curves. Given the sequence of curves in $\mathbb{R}^n:$ $\{ x_{1}^2+x_{2}^2+\cdots + x_{n}^2 = 1, ...
0
votes
1answer
23 views

Finding the inverse of a recursive function?

Let's say I have this function $$f(x) = \sum_{i=0}^{x-1}f(i)$$ provided $f(0) = 0, f(1) = 1$ and $x \in \mathbb Z$. This function is evidently one-to-one on $[3, \infty) $. Is there an inverse to this ...
0
votes
4answers
48 views

How to prove the sequence given by $a_{n+1}=s+a_n^2$ is monotonic increasing?

Let $s$ be $0\:\le \:s\le \:\frac{1}{4}$ and consider this sequence: $a_1\:=\:s$ $a_{n+1}\:=\:s\:+\:a_n^2$ I want to prove that is monotonic sequence, so I thought about induction or assume in ...
2
votes
4answers
34 views

General Solution for a non-Homogeneous Recurrence

What is the general solution to the recurrence: $$x(n + 2) = x(n + 1) + x(n) + n - 1$$ where $n\geq 1$ with $x(1) = 0, x(2) = 1$? It's a question on a practice exam I'm reviewing and I'm not ...
0
votes
1answer
26 views

Stuck on a difference equation which requires an A-level method

In the non-zero sequence $x[n-1]+x[n+1]=ax[n]$ and $x[n+4]=-x[n]$ i) Find possible values of $a$. ii) For what values of $b$ is $b^n$ a solution ($x[n]=b^n$)? I need to solve this using only ...
0
votes
0answers
33 views

2nd order difference equation with n dependent coeff

I wanted to know if there was and solution to the following equation. $\left(N-n+1\right)E_{n+2} - NE_{n+1} + \left(n+1\right)E_{n} + N = 0$ Where $E_0 = 0$ and $E_1 = 2^N - 1$. $N$ is just a ...
2
votes
1answer
24 views

Number of ternary strings without consecutive zeroes

I am looking for a number of ternary strings of length n, that dont contain consecutive zeroes. This was already asked, but I am NOT looking for reccurence relation. Instead, I found this formula, ...
2
votes
1answer
40 views

Recurrence equation - floor problem

I'm having trouble solving this recurrence equation: $$x(n) = x\left(\left\lfloor \frac n2\right\rfloor \right) + n,\quad x(1)=1$$ I`m trying to find non-recurrence equation: $$x(n) = 2n - 1$$ But ...
0
votes
1answer
42 views

$\lim_{n\rightarrow \infty} a_n$ for $ a_{n+1} =a_n\cdot \frac{6+a_n}{3+2a_n}$

let there be $a_1=3$,$a_{n+1} =a_n\cdot \frac{6+a_n}{3+2a_n}$ so $a_1=3,a_2=3,etc...$ let assume there is a limit L so $L =L\cdot \frac{6+L}{3+2L}$ L=0,3 But that is not a proof, how do I continue ...
0
votes
2answers
21 views

Solving recurrence equations

Is there a method to determine the generating function for a mutually recursive recurrence equation? As an example, consider the following set if equations $$R_n = R_{n-1}+ 3P_{n-1}; R_0 = 3$$ ...
8
votes
4answers
173 views

Help with a recurrence with even and odd terms

I have the following recurrence that I've been pounding on: $$ a(0)=1\\ a(1)=1\\ a(2)=2\\ a(2n)=a(n)+a(n+1)+n\\ a(2n+1)=a(n)+a(n-1)+1 $$ I don't have much background in solving these things, so I've ...
-1
votes
0answers
34 views

Difference equation involving f(x+1)

Solve this equation: $B(n+1) = B(n) + iB(n) - M.$ hint: This equation can be solved by: a. Find the general solution of $B(n+1) = (1+i)B(n)$ b. Find a particular solution of $B(n+1) = B(n) +iB(n) ...
0
votes
0answers
54 views

$T(n) = T(n/2 - \log(n)) +1$ using Substitution Method

I have the following recurrence: $$T(n) = T(n/2 - \log(n)) +1$$ How can this be solved using the substitution method? I don't fully understand the theory of this method and I'm not sure how to apply ...
0
votes
1answer
35 views

Express recurrence in closed form

I am having trouble understanding the process of expressing the following recurrence in its' closed form. First of all, I do not really understand what "closed form" means. If someone could elaborate ...
5
votes
2answers
52 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: ...
0
votes
1answer
13 views

Recursion Relation Problem: Counting Database Identifiers Recursively

A valid database identifier of length $n$ can be constructed in three ways: • Starting with $A$ and followed by any valid identifier of length $n − 1$. • Starting with one of the two-character ...
0
votes
1answer
38 views

How can I find the order of growth of this recurrence: $T(n) =\sqrt{n}T\bigl(\sqrt{n}\bigr) + n$

I am trying to find the order of growth ($O(n)$, $O(n\log n)$) of the recurrence $T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + n$. I started to unroll the recurrence and found that I can rewrite it ...
0
votes
0answers
23 views

$T(n) = 4T({n/2}) + n \log{n}$ using substitution method

can you help me please with solving recurrence $T(n) = 4T({n/2}) + n\log{n}$ by substitution method? By using Master theorem I know the result is $\theta(n^2)$. So I need to prove that $T(n) \leq ...
1
vote
2answers
29 views

Example of recurrence relation without closed form expression?

Can give an example of a recurrence relation for which there does not exist a closed form expression?
4
votes
2answers
45 views

If $f_1(k)=\sum_{i=1}^k\frac{1}{i}$ and $f_n(k)=\sum_{i=1}^kf_{n-1}(i)$, then what is $f_n(n)$?

Let $$f_1(k)=\sum_{i=1}^k\frac{1}{i},$$ and define inductively $$f_n(k)=\sum_{i=1}^kf_{n-1}(i).$$ So, $$f_2(k)=\sum_{i_2=1}^k\sum_{i_1=1}^{i_2}\frac{1}{i_1},\quad ...
1
vote
4answers
68 views

Recurrence Relation $k_{n+2}=\frac{1-n}{n+2}k_n$

There was an interesting question posted on here earlier today but it seems to have disappeared. With due to respect to the OP, I'll post the same question here from memory. If anyone finds the ...
1
vote
0answers
39 views

How to solve this tough recurrence relation?

For solving a related probability problem, I'm required to solve the following recurrence relation:- $q(r,b,L)=\frac{b}{r+b}q(r,b-1,L)+\sum_{k=1}^{L}\frac{r}{r+b}\times\cdots \times ...
2
votes
1answer
21 views

recurrence relation sequence..stuck

Q-->Find a recursive solution for $S_n$ the number of sequences of length $n$, composed of the letters $a$, $b$ or $c$ in which no sequence contains consecutive b's. Give detailed explanations. what ...
0
votes
2answers
33 views

Number of ways to color a sequence of squares so that no two black squares are adjacent

A sequence of squares may be colored so that each square is black or white. Let $S_n$ be the number of ways of coloring the sequence so that no two black squares are adjacent. Find a recursive ...
0
votes
1answer
41 views

Understanding a recurrence relation

I want to understand the following recurrence relation from https://oeis.org/A140993. I see the triangle it creates, but I don't understand how to generate the triangle from the formula. Can someone ...
2
votes
1answer
52 views

Finding matrix for given recurrence [closed]

For the recurrence relation: $f(0)=1$ $f(1)=1$ $f(2)=2$ $f(2n)=f(n)+f(n+1)+n$ $f(2n+1)=f(n)+f(n−1)+1$ How to find square matrices $M_0, M_1$ and vectors $u, v$ such that if the base-2 expansion ...
0
votes
0answers
50 views

Solution of $x_{k+1} = x_{k} (a x_{k} + b)$

Could anyone help me to solve the equation $x_{k+1} = x_{k} (a x_{k} + b)$, for find the explicit solution of $x_{k}$? BTW. Do you know a GOOD book for the classification for non linear difference ...
0
votes
0answers
9 views

Has anyone come across a non-constant population SIR model with infected birth?

I've come up with a seemingly new type of SIR model for one of my classes which allows for non-constant population and infected members to birth more infected members (such as is the case for many ...