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

learn more… | top users | synonyms (2)

-1
votes
1answer
18 views

Looking for help in regard to Series solutions with ordinary points (ODE)

I have a question that is in regard to the final answers/answer that one is to get when solving some ODE questions via series. I am having some confusion on what if I am doing is correct/ why it is or ...
4
votes
1answer
83 views

Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...
1
vote
0answers
8 views

Optimizing an asymptotic recurrence relation with two recursive terms

I have a recurrence relation that looks like this: $T(n) = 2 T(c n) + T((1-c)n) + O(n)$ The base case is just $T(b) = 1$ when $b \leq 1$. I'm trying to figure out the best value of $c \in (0, 1)$ ...
1
vote
1answer
48 views

Solving a recurrence relation using generating functions

My recurrence relation is D(n) = D(n 􀀀- 1) + D(n - 2) + 5(n -􀀀 1); with the initial conditions D(2),D(3) being 6, 17 respectively. The generating function G(z) for the sequence D(n) is given I ...
1
vote
2answers
428 views

Find recurrence relation for ternary strings that don't have substrings 00, 01 and last symbol is not 0

I am preparing for my finals for discrete mathematics and I came across this exercise in textbook. Let $s_{n}$ denote all ternary strings of length $n$, such that any string in $s_{n}$ does not ...
2
votes
2answers
165 views

Proof by induction that $x_n>2$ where $x_{n+1}=\frac{2x_n^2 +4x_n -2}{2x_n+3}$

The sequence $x_1$ $x_2$ $x_3$..... is such that $x_1=3$ and $$x_{n+1}=\frac{2x_n^2 +4x_n -2}{2x_n+3}$$ Prove by induction that $x_n>2$ for all $n$. First I proved the base case using $n=1$ as ...
1
vote
2answers
62 views

How to solve the difference equation $u_n = u_{n-1} + u_{n-2}+1$

Given that: $$ \begin{equation} u_n=\begin{cases} 1, & \text{if $0\leq n\leq1$}\\ u_{n-1} + u_{n-2}+1, & \text{if $n>1$} \end{cases} \end{equation} $$ How do you solve this ...
2
votes
1answer
159 views
+50

Result of a $2D$ random walk with position dependent probabilities

I was just wondering about $2D$ random walks when I got the idea of a position dependent $2D$ random walk: A man is initially at $(x,y)$ and can move in a line parallel to the X and Y-axis only. ...
2
votes
1answer
30 views

How to determine the generating function?

So I have $$\overset{*}{F} = \overset{*}{F}_{n-1} + \overset{*}{F}_{n-2} + g(n)$$ where $\overset{*}{F}$ is NOT a Fibonacci number for $n \geq 2$. $g(n)$ is any function $g: \mathbb{N} \to ...
0
votes
2answers
34 views

Limit of a sequence defined by a non-linear recurrence relation

How can one find the limit for the sequence $\{x_n\}^{+\infty}_{n=0}$ where $$x_0 = 0, x_1 = 1, x_{n+1} = \dfrac{x_n + nx_{n-1}}{n+1}$$ By computing the values I came to the conclusion that it ...
2
votes
1answer
327 views

How to find a closed form formula for the following recurrence relation?

I have to find a closed form formula for the following recurrence relation which describes Strassen's matrix multiplication algorithm - $$T(n) = 7\,T\left(n \over 2\right) + \frac{18}{16}n^2$$ with ...
5
votes
1answer
197 views

The recurrence $a_k(n) = \sum_{0\leqslant j<n} a_{k-1}(n+j)$

I'm trying to find a closed form expression to the following recurrence relation: \begin{align} &a_k(0) = 0, \quad \forall k\geqslant 1; \\ &a_k(1) = 1, \quad \forall k\geqslant 1; \\ ...
0
votes
2answers
53 views

Simplifying recurrence relation $T_{n+1}=20T_n-48\times 8^n$

So I have the recurrence relation $$T_{n+1}=20T_n-8^n48.$$ For $T_0 = 6$, the first terms are $72$, $1056$, $18048$. I've seen a few worked examples for simplifying other recurrence series, but I'm ...
9
votes
2answers
132 views

Does equation $f(g(x))=a f(x)$ have a solution?

Suppose $g: [0,1] \to [0,1]$ is a strictly increasing, continuously differentiable function with $g(0)=0$ and $g(1) < 1$, and $a \in (0,1)$. Is there a function $f:[0,1] \to \mathbb{R}$ such that ...
1
vote
2answers
48 views

Wolfram alpha giving wrong result on recurrence?

I have the recurrence$$a_{n+2}-a_n=1$$ The answer I got was $a_n=A+B(-1)^n+\frac n 2$, while WolframAlpha is giving me $a_n=A+B(-1)^n+\frac n 2- \frac 1 4$. Although when I plug them in the ...
1
vote
2answers
52 views

Finding the limit of a recursively defined sequence (recurrence relation). Specifically and generally

Whilst reading Goldrei's Classic Set Theory, I have come across a recursively defined sequence $a_0=0, a_1=1, a_n=\frac{1}{2}\left(a_{n-1} + a_{n-2} \right) $ The first few terms of which are: $0, ...
0
votes
2answers
39 views

A non-homogeneous recurrence of Fibonacci sequence

I am working on Fibonacci sequence (recursively) But the hack is that I have the following non-homogeneous version: $$F_n =F_{n-1} +F_{n-2} +g(n)$$ Where: $F_1=g(1)$ $F_0=g(0)$ I have to use: ...
0
votes
3answers
31 views

Finding particular solution when solving recurrence relation

I have a question about how to find the particular solutions when trying to solve recurrence relations. For example, trying to solve $$ a_{n+2} = -4a_n + 8n2^n $$ I begin with finding the roots in ...
4
votes
2answers
59 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 ...
0
votes
1answer
36 views

Recursive Equation Indexing

I'm trying to write a recursive equation/formula with all natural numbers as input but I need to exclude every number ending in a $4$ or $9$ ($n= 5i-1$, $i \in \Bbb N)$ and exclude all numbers $n= ...
-1
votes
1answer
40 views

How to find Difference equation of this block diagram. PLEASE HELP! [on hold]

Can anyone please help me with this question. Like for part b), it says i need to convert all the z terms to negative powers. How do i do that and how do i find the transfer function?
1
vote
0answers
17 views

Lines and planes-recursive formula

A family of $n$ lines is drawn in the plane such that each pair of lines cross and no $3$ dinstinct lines have a point in common Let $r(n)$ denote the number of regions into ...
1
vote
0answers
50 views

How I can make a proof to this conjecture if it is possible?

Is there someone who can show me the way helping me to proof this conjecture. If it's not open, at a least show me links or papers which to be helpful. Conjecture: Assume $c > 0$ and that an ...
0
votes
1answer
15 views

Explanation of Linear Nonhomogeneous Recurrence Relations Problem

$$5\times 3^n=v_{n+2}-6v_{n+1}+9v_n$$ $$=C(n+2)^23^{n+2}-6C(n+1)^23^{n+1}+9Cn^23^n$$ $$=18C3^n$$ Can anyone explain to me how he got $18C3^n$. I've been simplifying the 2nd step but haven't gotten ...
0
votes
1answer
19 views

Looking for a “nice” Recurrence relation…

I'm want to build a game (with steps) that the solution have a Recurrence relation, i.e. - to solve the game you have to move from point A to point B, from point B to point C...(kind of a maze). Of ...
0
votes
1answer
24 views

Recurrence equation $f(g\cdot x)/f(x)=t$

I am trying to solve equation $\frac{f(g x)}{f(x)}=t$ and I'm out of ideas. Any suggestions? In my problem, $f$ is a continuous and weakly increasing function.
1
vote
1answer
21 views

Step by step Linear Reccurence

Can someone explain to me in a little bit more detail how you can get to this point. I know its explained here but i'm trying to apply the way he did this problem to this one \begin{equation*} ...
2
votes
1answer
57 views

How to find the recurrence relation from a given polynomial?

Consider the formal power series: $A(x)=\sum a_nx^n$. and $A(x)= \frac{8+14x-50x^2}{1-7x^2+6x^3}$ I am trying to derive a recurrence relation, Is there a general method for doing it? Please help, ...
0
votes
0answers
27 views

how to solve T(n)=T(Logn)+O(1)

Given That $T(1)=1$ Solve following recurrence function $T(n)=T(\log n)+O(1)$ I know the answer is $\log^* n$ but don't know how to prove it. What I tried: $\log(n)+\log(n-1)+\log(n-2)+...+1 = ...
0
votes
1answer
26 views

Quick Factoring/Multiplying with recursion question

I am wondering if anyone can help to shed some light on something that I think should be very easy but I dont quite understand. In my textbook, how does author make this conclusion, From $$ ...
4
votes
2answers
37 views

How many ways to stack $n$ boxes of 4 colours so that no $2$ blue boxes are consecutive.

Let $X_n$ denote the number of ways to stack red, white and blue and green boxes, find the ways to count the ways of stacking n boxes, with no consecutive blue boxes. My attempt: Let $X^R_n$ denote ...
2
votes
1answer
36 views

How do I find an analytic solution to this recursive function?

I was playing with some recurrence relations, and I ended up with this a long nested function. How can I generalize the following relationship: $$ f_n = a + \frac{b}{f_{n-1}} $$ $$ f_1 = a + ...
0
votes
0answers
51 views

Solve the following recurrence relation in two variables

How to solve this recurrence $$S(m,n)=S(m,n-1)+S(m-1,n-1)+S(m-1,n)$$ with base conditions $$S(1,1)=3,\; S(0,n)=S(m,0)=1.$$ This recurrence came up when I tried to solve this problem: Find the ...
4
votes
2answers
50 views

Name for the following set of polynomials

I have the following set of polynomials defined by $$P_n(x) = \sum^n_{k = 0} \frac{n!}{k!} x^k, \quad x \geqslant 0.$$ The first few are \begin{align*} P_0 (x) &= 1\\ P_1 (x) &= 1+x\\ P_2 (x) ...
4
votes
2answers
47 views

Triangular Array's Recursive Formula Breakdown

I have the following polynomials: $$1$$ $$z-1$$ $$z^2-2z+3$$ $$z^3-3z^2+9z-15$$ $$z^4-4z^3+18z^2-60z+93$$ $$z^5-5z^4+30z^3-150z^2+465z-725$$ $$...$$ They are generated both recursively and explicitly. ...
4
votes
0answers
57 views

What is the explicit formula (solution) to this recursively defined binary matrix?

My question concerns the following binary matrix (call it matrix $A$). Or rather the entire family of such matrices, for some number of columns $n$ and rows $2^n$. The ellipses indicate that the ...
3
votes
1answer
439 views

Recurrence Relation, Discrete Math problem(Homework)

There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have ...
0
votes
0answers
20 views

Find $v_k$ the probability of absorption at $N$ if the walk starts at $S_0=k$ for $0 \leq k \leq N$

Supose that $(S_n)_{n\geq0}$ is a random walk on $\{0,1,2,\dots,N\}$ with up prbability of $p$ and down probability of $(p-1)$. Find $v_k$ the probability of absorption at $N$ if the walk starts at ...
1
vote
4answers
180 views

Proof the golden ratio with the limit of Fibonacci sequence [duplicate]

Let $F_n=F_{n-1}+F_{n-2}$ the Fibonacci numbers, and $\phi=\frac{1+\sqrt5}{2}$ The exercise asks me to prove that: $\lim\limits_{n \to \infty}\frac{F_{n+1}}{F_n}=\phi$. Sorry as can be proceed??
2
votes
2answers
20 views

Proving two Recurrence Relations

I encountered this problem in the International baccalaureate Higher Level math book, and my teacher could not help. If anyone could please take the time to look at it, that would be great. I need ...
0
votes
0answers
12 views

Lyapunov function for discrete dynamical system

Consider the ODE \begin{equation} \dot{x}(t) = h(x(t)), \end{equation} where $h: \mathbb{R}^d \to \mathbb{R}^d$ is a continuously differentiable map. Let $x^*$ be an asymptotically stable ...
1
vote
2answers
43 views

solve recurrence relation: comparisons to construct binary search tree with maple

I would like to solve the recurrence relation for the average number of comparisons necessary to the construction of a binary search tree. the recurrence is $$ i(n) = n - 1 + \frac{2}{n} ...
0
votes
1answer
19 views

First order differential equation to standard form conversion

I need to convert the following differential equation to standard form. $$ T_n = 2 T_{n-1}+1 $$ (not quite sure how to really format it properly) I was thinking it is $$ T_n - 2T_{n-1} - 1$$ If ...
1
vote
2answers
28 views

Series definied by recurrence relation

Define a sequence recursively by $$\large{a_1 = \sqrt{2},a_{n+1} = \sqrt{2 + a_n}}$$ (a) By induction or otherwise, show that the sequence is increasing and bounded above by 3. Apply the monotonic ...
6
votes
1answer
117 views

What are the solutions for $a(n)$ and $b(n)$ when $a(n+1)=a(n)b(n)$ and $b(n+1)=a(n)+b(n)$?

If you have the following recurrence relations : $a(n+1)= a(n) b(n)$ $b(n+1)= a(n) + b(n) $ How do you find the form of $a(n)$ and $b(n)$ ? I suspect there isn't a closed form , but a infinit sum ...
0
votes
1answer
62 views

A recurrence for a combinatorial problem

$N$ balls are tossed into $n$ boxes independently. Each ball has a $1/n$ chance of falling into any box.$$P_{N,n}(k):= Pr\{exactly\:k\:empty\:boxes\:after\:N\:balls\:thrown\:into\:n\:boxes\}$$ Show ...
0
votes
1answer
48 views

Problem with Recurrence Relations

A particle P executes a random walk on the line above such that when it is at point $n$ ($1 \leq n \leq 9$, $n$ a non-negative integer), it has a probability of $0.4$ of moving to $n+1$ and a ...
2
votes
0answers
37 views

How many entries in the sequence $x_n$ given by recursion $x_1=1\ ,\ x_{n+1}=p_{x_n}$ are known?

The sequence $x_n$ with the recursion $x_1=1\ ,\ x_{n+1}=p_{x_n}$ , where $p_k$ denotes the $k-th$ prime, has the following values : ...
1
vote
3answers
87 views

nth element of recurrence relation

I need to find explicit equation, that will give me n-th element of this recurrence: $$ a_0=0\\ a_1=3\\ a_{n+2}=a_{n+1} + 2a_{n} $$ I know, that I can use generating functions and difference ...
6
votes
1answer
51 views

The number of series over $\{0,1,2\}$ without repeating numbers

What is the number of series over $\{0,1,2\}$ with length $n$ without repeating the same number one after the other ($22$ is not allowed but $101$ is), that does not begin and end with the number $2$. ...