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

learn more… | top users | synonyms (2)

0
votes
0answers
6 views

recursive definition for two mutually exclusive events

How do we write recursive definitions for two mutually exclusive events ? Can anyone explain with some examples as how do we come up with solutions in case of exclusive events ?
1
vote
2answers
55 views

Generating function for $\sum_{n=0}^{\infty} n^{p} x^n$

I am trying to derive the generating function for $H(x,p) = \sum_{n=0}^{\infty} n^p x^n$ I am trying to solve it with the following logic: (Edited now, trying a new framing) Base case: $$H(x,0) = \...
8
votes
1answer
57 views

A pair of sequences defined by mutual addition/multiplication

Define sequences $\{a_n\},\,\{b_n\}$ by mutual recurrence relations: $$a_0=b_0=1,\quad a_{n+1}=a_n+b_n,\quad b_{n+1}=a_n\cdot b_n.\tag1$$ The sequence $\{a_n\}$ begins: $$1,\,2,\,3,\,5,\,11,\,41,\,371,...
5
votes
1answer
57 views

Deriving sum of powers formula using generating functions

Just for fun I wanted to try to derive a formula for the sum of $p$-powers using generating functions, but without using any literature or websites for help. However I do need a small push or hint. ...
-1
votes
0answers
27 views

How do I obtain the running time for $T(n)=n^2 \sqrt{n}$?

I tried as, $$T(n)=n^2 \sqrt{n} =n^{\frac{5}{2}} $$ On expanding, $$ T(n)=n^{\frac{5}{2}}+n^{(\frac{5}{2})^2}+n^{(\frac{5}{2})^3}+\cdots +n^{(\frac{5}{2})^k} $$ Thus, for $T(1)$ $$n^{(\frac{5}{2})^k}=...
-1
votes
1answer
29 views

Number of solutions of the two equations

Find the number of integral solutions of the equation: $a+b+c=m$ with $0\gt a\gt b\gt c$ And the generalized version: $a_1 + a_2 + \cdots + a_k = m$ with $ 0\gt a_1\gt a_2\gt \cdots \gt a_k$
1
vote
1answer
50 views

Factories processing jobs

We have two factories that can process jobs; each job takes two days to complete. The factories agree on a minimum threshold $a\in[0,1]$ to accept jobs. Every day, a value $v\in[0,1]$ is drawn ...
1
vote
0answers
14 views

CLRS substitution method “subtracting constant” technique

I'm reading CLRS, and in Chapter 4 it states that if you guess the asymptotic complexity of a recurrence correctly but cannot quite get the mathematical induction work out, a common method to employ ...
1
vote
0answers
32 views

Proving that this recursively defined sequence converges.

The sequence is defined as such, with $a_1=1$, $$ a_{n+1} = \begin{cases} a_n + 1/n, & \mbox{if } a_n^2 \leq 2 \\ a_n - 1/n, & \mbox{if } a_n^2 > 2 \\ \end{cases}. $$ In the book, P.M. ...
0
votes
0answers
29 views

Big O for $T(n) = T(n/2) + 2T(n/4) + O(n)$?

How can I solve the recurrent relation $T(n) = T(n/2) + 2T(n/4) + O(n)$? I don't want to make $2T(n/4) = T(n/2)$. Some searching tells me I should try the Master Theorem. Is there a more intuitive ...
1
vote
1answer
23 views

How do I convert the following relation into a recurrence relation?

I am trying to analyse the time complexity of the fast exponentiation method, which is given as $$x^n= \begin{cases} x^\frac{n}{2}.x^\frac{n}{2} &\text{if n is even}\newline x.x^{n-1} &...
4
votes
1answer
34 views

When is a recurrence the sum of the powers of the roots of a polynomial?

Newton's formula allows one to calculate the sum $S_n(P)$ of the $n$th powers of the roots of a given monic polynomial $P$ without finding the roots explicitly. (This works even when the roots ...
1
vote
2answers
78 views

Help solving this recurrence relation

I wanted to resolve the determinant of the next (nxn) matrix via recurrence relations: $$ \begin{vmatrix} a & 1 & 0 & 0 & 0 & 0 &.... 0 & 0 & 0 & 0 & 0\\ 1 &...
0
votes
1answer
19 views

recurrence relation - How to determine pattern for an even or odd or different type of factorial

Hi I am having trouble on how to solve for the odd terms of recurrence relation in terms of exponential and factorials. How are you able to see a pattern to simplify a non standard factorial. This ...
-1
votes
0answers
11 views

Complex and real conditions on steady state stability analysis

I am currently working on a model and I'm trying to find conditions on stability for a point n*. The model is a non-linear difference equation and after calculating and simplifying |f'(n*)|<1 I am ...
2
votes
1answer
32 views

If $2a_{n+2} \le a_{n+1}+a_n$, then $\lim \sup a_n \le \frac23 a_2 + \frac13 a_1$

This is a reformulation of a deleted question: If $a_1 > 0$ and $a_2 > 0$ and $2a_{n+2} \le a_{n+1}+a_n$, show that $\lim \sup a_n \le \frac23 a_2 + \frac13 a_1$. My proof involves showing ...
1
vote
1answer
30 views

Coverings of a rectangle

How many coverings of the rectangle with height $1$ and length $n$ exist, if we use only tiles with height $1$ of the following 6 types: The solution should be in a closed form (formula).
0
votes
2answers
64 views

Solve recurrence relation $a(n) = -a(n - 2) + \cos({n} \cdot {\frac{\pi}{2}})$

Given recurrence equation $$a(n) = -a(n - 2) + \cos({n} \cdot {\frac{\pi}{2}})$$ find the closed form solution. Here is my attempt. First solve the homogeneous equation: $$a^{(0)}(n) = -a^{(0)}(n - ...
1
vote
2answers
37 views

How to solve this recurrence $T(n) = \log{n}*T(n/\log{n})+\sqrt{n}$

I tried substitution for $2^n$ or $2^{\log{n}}$ or even $2^{2^n}$ and it didn't work. Thanks! :)
1
vote
0answers
28 views

Finding functions that give nice solutions to a recurrence relation.

In a recent problem I was working through, I came across the following recurrence relation: $$ \text{K}_1(x,\ t;\ g) = 1,\quad x, t\in\Bbb{R}\quad g\in\text{C}^1 \\ \text{K}_{n+1}(x,\ t;\ g) = g'(t)\...
0
votes
1answer
50 views

Thought-provoking functional computation problem

I have been assigned a very thought-provoking functional computation problem (to be completed $without$ a calculator) which has left me essentially stumped—that is, I really can't come up with an ...
2
votes
3answers
35 views

Trying to solve non-homogeneous linear recurrence relation with difficult non-homogeneous part

I have the following recurrence relation that I'm trying to solve: $$f(n)=2f(n-1)-f(n-2)-2$$ The homogeneous part is easy: The characteristic polynomial $r^2-2r+r=0$ has root $r=1$ with ...
0
votes
0answers
19 views

What is the method for solving this recurrence relation?

I have an equation for generating square-triangle numbers using a recurrence relation: $$f(n)^2+f(n)(2-34f(n-1))+(f(n-1)^2-70f(n-1)+1) = 0$$ But I wish to solve the equation to produce a closed form ...
0
votes
0answers
32 views

How can I solve this recurrence relation for generating triangle-squares?

$$N_k = 17N_{k-1} + 6(8N^2_{k-1} + N_{k-1})^{1/2} + 1$$ $$k\geqslant 1$$ I'm trying to convert a recurrence relationship for producing triangle square-numbers into a closed-form expression in terms of ...
0
votes
1answer
41 views

How to solve this recursion?

If $r>0$ holds and recursion is given by $T(r)=\alpha T(r^{1/\alpha})+\alpha r^{1/\alpha}$ where $\alpha\geq 2$ is fixed and assume $T(r)=O(1)$ for $r\leq1$. What is $T(r)$?
1
vote
4answers
84 views

Closed form of recurrence relation $F(n) = 2 + F(n-1) + F(n-2)$

I was figuring out an answer to the question, How many Boolean arrays of length $n$ could be formed if there are to be no two falses in a row? I could see that it boils down to a Fibonacci ...
0
votes
2answers
26 views

Finding the generating function of a recurrence relation in dependence of a variable

Given this inhomogeneous linear recurrence relation of 2nd order : $F_n = F_{n-2} + a$ for $n \geq 2$ with $F_1 = 1$ and $F_0 = 0$ How do I find the generating function of this recurrence ...
0
votes
0answers
9 views

2D recurrence relation

Lately I encountered following DE: $$ x O^\alpha f\left(x\right) = f\left(x\right)-1 $$, where $$ O f\left(x\right) = x f'\left(x\right) + f\left(x\right) $$ It can be solved using a solution to the ...
1
vote
1answer
31 views

Josephus problem: the renumbering method from Concrete Mathematics

In Concrete Mathematics, Chapter 3, Section 3, an interesting method to solve the Josephus problem is discussed. The paragraphs below depict the method, which are extracted from the book: (Initially, ...
0
votes
1answer
67 views

$a_{n+1} = (a_n+1)a+(a+1)a_n+2\sqrt{a(a+1)a_n(a_n+1)} \quad (n = 1,2,\ldots).$

Let $a$ be a positive integer and $\{a_n\}$ be defined by $a_0 = 0$ and $$a_{n+1} = (a_n+1)a+(a+1)a_n+2\sqrt{a(a+1)a_n(a_n+1)} \quad (n = 1,2,\ldots).$$ Show that for each positive integer $n$, $a_n$ ...
1
vote
0answers
61 views

Solving a non-standard linear recurrence [closed]

Can you find an expression for the sequence $(a_n)$ satisfying the following recurrence $$a_n = a_{n-1} + a_{n-2} + \sum_{i=3}^{n} 2\binom{n}{i}a_{n-i}$$ for $n \geq 3$ where $a_0 = 0, a_1 = 1, a_2 ...
2
votes
0answers
25 views

Is it possible to find the nth term of this recursive sequence?

I have the following sequence: $$x_n= y - sgn(x_{n-1}) \cdot |b\cdot x_{n-1} - c|^{0.5}$$ $$x_1=0$$ Is there a way to find $x_n$ without knowing $x_{n-1}$?
0
votes
0answers
37 views

Proving that one sequence is greater than another using a recurrence inequality

I'm trying to understand the proof of proposition 2 from All reductive p-adic groups are tame, Bernshtein. In the article there are given two sequences of functions $\{{f_l}\}_{l=0}^\infty$, $\{{\...
1
vote
1answer
32 views

Using determinants to find a recursive sequence

I am trying to compute a three diagonal determinant in order to find the recursive relation. Let $\Delta_{n}$=$\begin{vmatrix} 11 & 3 & 0 & 0 & \dots & 0\\ 13 & 11 & 3 &...
1
vote
0answers
44 views

Solving recurrence relation $a_n=1 + \sum\limits_{i=1}^{n-1}ia_{n-i}$ with $a_1=1$

Consider the recurrence relation $$a_n=1 + \sum_{i=1}^{n-1}ia_{n-i}$$ with initial term $a_1=1$. What is $a_n$? I tried to guess some closed formula from the first 6 terms, which are $1$, $2$, $5$, $...
0
votes
1answer
23 views

Solving Recurrence Relations with generating functions when the variable is in the function.

I'm studying for a midterm and couldn't figure out these three recurrences that I came across: $i_{n+1}=2ni_n+2i_n+2$ with initial condition $i_0=1$ $j_{n+1}=3j_n+1$ with initial condition $j_1=1$ $...
0
votes
2answers
28 views

Recurrence: Theta of t(n) = 4t(n-1) -15

First let me start off by saying that I am using the substitution method to solve this equation.Although any other methods will be welcomed, this is just the particular method I feel comfortable with. ...
0
votes
1answer
21 views

Express $T(n) $as a recurrence relation and derive and expression for $T(n)$ in terms of $n$.

Question: $T(n)$solves the problem by breaking it up into 4 sub problems of the same kind, each of size $n/4$. The solution to the original problem is obtained by combining the solutions of the $4$ ...
0
votes
2answers
37 views

how many sequences above 1,2,3,4,5,6,7 that don't contain odd couples

I got stucked a little with this question. would appreciate your help. the question is "find a recursive relation that counts how many sequences of order n above ${1,2,3,4,5,6,7}$ that don't contain ...
0
votes
3answers
69 views

Find recurrence relation with general solution $a_n=A+Bn+C2^n+\frac{1}{3}n2^{n-1}$

General solution is: $a_n=A+Bn+C*2^n+\frac{n}{3}*2^{n-1}$ Can you give me some tips on solving this? Any help would be appreciated.
1
vote
1answer
71 views

second-order difference equation with variable coefficients $ax_{n+1}-(n+1+a)x_n+nx_{n-1}=-n$

The equation is: $ax_{n+1}-(n+1+a)x_n+nx_{n-1}=-n$, where $a$ is a constant and $0<a<1$. Any ideas on how to solve it? May be the z-transform is useful? Thank you! Using the difference operator ...
0
votes
0answers
90 views

Solutions to recurrence relations

Consider functions $s_{m},c_{m},d_{m}$ defined by the following recurrence relations $$s_{1}=n$$ $$c_{1}=s$$ $$d_{1}=0$$ $$s_{2}=n$$ $$c_{2}=s-n$$ $$d_{2}=d$$ $s,n, d$ are integers. If $c_{m}>...
0
votes
4answers
57 views

Prove for all $ n\in \mathbb{N} $ ,$n ≥ 1, a(n)$ is odd.

Prove for all $n\in\mathbb{N}\backslash \{0\}$, $a(n)$ is odd. Consider the sequence defined as followed: $a(1)= 1$ $a(2)= 3$,where $n \in \mathbb{N}$ $$a(n)=a(n-2)+2a(n-1), n ≥3$$ Conjecture: ...
2
votes
1answer
55 views

Linear four-parameter recurrence from Concrete Mathematics

In the book Concrete Mathematics, there's an exercise (1.16) where you're asked to solve a general four-parameter recurrence using the Repertoire Method. The recurrence is defined as follows: \begin{...
0
votes
2answers
41 views

How can I solve this exponential recurrence relation?

Does anyone know how to solve $a_{n+1}=1-Ce^{-a_n}$ explicitly for $a_n$ in terms of $n$ and $a_0$, where $C$ is constant?
3
votes
3answers
98 views

Recurrence relation solution $a_{n}=\frac{a_{n-1}}{a_{n-1}-a_{n-2}}$

I want to find the analytic form of the recurrence relation $$a_{n}=\frac{a_{n-1}}{a_{n-1}-a_{n-2}},\,a_{1}=2,\,a_{2}=1 $$ but when looking at the results they seem chaotic. Is it possible that it ...
2
votes
1answer
40 views

I need a common term for a recursive sequence

Some days ago, I made a question here about a common term for recursive sequence. I gained very good solutions. Thanks again. Today, I was thinking of a general case which is given below. Assume $p$ ...
1
vote
5answers
56 views

Solving $a_n = a_{n-1} + 7n$ for $n\ge1$ and $a_0 = 4$

First, I found the homogeneous solution: $$r^n - r^{n-1} = 0$$ $$\Rightarrow r = 1$$ So the homogeneous solution is of the form: $$c(1)^n = c$$ Then, to find a particular solution, I "guessed" the ...
0
votes
1answer
24 views

Linear combination of sequence related to Fibonacci

Let $a= \frac{1+\sqrt{5}}{2}$ and $b= \frac{1-\sqrt{5}}{2}$. Prove that for all $c,d \in \mathbb{N}$ that $g_n = ca^n + db^n$ satisfies $g_{n+2} = g_{n+1} + g_{n}$ for all $n\in \mathbb{N}$. I'm ...
1
vote
0answers
27 views

Lucas recurrence relation

Lucas recurrence relation is defined as: $V_n = PV_{n-1} – QV_{n-2}$; for $V_0 = 2; V_1 = P$ Here $P$ is positive integer and $Q = {-1, 1}$ or may be $+1$ or $-1$ A Fibonacci Pseudo prime with ...