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

learn more… | top users | synonyms (2)

1
vote
1answer
35 views

Difference equation formula $\sum a^t = \frac{a^t}{a-1}$.

As I explain below, this question was originally posted by user YYG, but then deleted. I am reposting the question (from memory) and I will answer it myself below. Question: In Difference Equations ...
2
votes
0answers
141 views

Special map $f(x_n)=x_{{n+1} [\mod 4]}$

As mentioned in the headline I am considering the map $f(x_n)=x_{{n+1} [\mod 4]}$. It looks a little bit similar to the dyadic (bernoulli) map but instead of $\mod 1$ we have $\mod 4$ which means that ...
4
votes
1answer
78 views

Find recursive forumula for integrals

I have to find recursve formulas for solving the following two integrals. The assignment tells one to find an Expression that leads from the calculation of $\dfrac{I_{2n}}{I_{2n+1}}$ to the ...
1
vote
3answers
139 views

$W_n=\int_0^{\pi/2}\sin^n(x)\,dx$ Find a relation between $W_{n+2}$ and $W_n$

Set $$W_n=\int_0^{\pi/2}\sin^n(x)\,dx.$$ Compute $W_0$ and $W_1$. Find a relation between $W_n$ and $W_{n+2}$ and deduce a formula for $W_n$. What I have so far is: $$W_{2k}=\frac{1}{2^k}\left( ...
1
vote
1answer
80 views

Prove any $k\in\mathbb{N}$ can be created using sum of $a_{n}=2a_{n-1}-\left\lfloor \frac{a_{n-1}}{2}\right\rfloor ,a_{1}=1$

I need to prove that any integer can created using a sum of elements in $a_{n}=2a_{n-1}-\left\lfloor \frac{a_{n-1}}{2}\right\rfloor ,a_{1}=1$ without repetition. My attempt was just bad... I've ...
0
votes
1answer
136 views

Period of recurrence relation mod p

For a recurrence relation like $$f(n)=((k-2)*f(n-1)+(k-1)*f(n-2) )\bmod p$$ with initial conditions .This recurrence holds for n>=4 $$\begin{align}f(1)&=k \bmod p\\ f(2)&=k*(k-1) \bmod ...
4
votes
1answer
140 views

Recursive sequence with binomial coefficients

I have a sequence $\epsilon_i$ defined recursively for $i\ge 1$ as follows \begin{eqnarray*} \epsilon_1 &=& \frac{1}{p}\\ \epsilon_n &=& \frac{1}{1-(1-p)^n}\left( 1 + \sum_{j=1}^{n-1} ...
2
votes
5answers
137 views

Finding a recurrence relation in combinatorics

First, my English is not that good so please don't laugh. I need to find a recurrence relation for : The number of words with the length of n that could be composed from the letters A,B,C,D, so the ...
2
votes
1answer
84 views

Recursive Definition for Logarithm

Is it possible to express $\log(n)$ in terms of itself, using only elementary functions, e.g., similar to (the incorrect made-up equation): \begin{equation*} \log(n) = e^n * \log(n - 1) + \sin(n) * ...
1
vote
2answers
47 views

Recursive function definition, how does my teacher arrive at this answer?

I am currently revising for my maths exam in school and there is a section on recursion. The question is explained as follows: $$f(m, n) =\begin{cases} n + 1 &\text{if } m = 0\\ f(m − 1, 1) ...
0
votes
1answer
95 views

How many words can you make with {1,2,3,4} such that difference between 2 letters is 1

Hello and happy new year. I've been struggling with this question and I really need some help. The question is, find a recurrence relation that demonstrates how many words of length $n$ can we write ...
2
votes
5answers
77 views

stuck trying to solve nonhomogeneous recurrence relation

hello and happy new year! I'm trying to solve this question: We are required to find the solution (direct formula) of the following recurrence relation: $b(n)=b(n-1)+n-1$, $b(0)=0$. What I did: I ...
2
votes
2answers
90 views

Does there exist an infinite sequence $p_0,p_1,p_2…$ of prime numbers such that $p_k=4 p_{k-1}\pm 1$

$k \in Z^+$ firstly we know that there exists infinetly many primes of the form $4n+1$ by FTA also we see that if we consider finite primes say to $n$ then the recursive formular can be expressed ...
0
votes
1answer
207 views

Solving recurrences with summation factors (Concrete Mathematics)

Chapter 2 in Concrete Mathematics talks about solving recurrences of the form $$a_{n}T_{n}=b_{n}T_{n-1}+c_{n}$$ by reducing them into a sum. The authors multiply both sides by a summation factor ...
4
votes
2answers
90 views

Recurrence equation for $(-1)^k k$

In a project of mine I came across the recurrence relation $$ a_{n+1} = 1 -(n+1)\sum_{k=1}^n{\frac{a_k}{n-k+1}\binom{n}{k}},\quad a_1=2; $$ From calculating the first few terms it seems obvious that ...
4
votes
3answers
651 views

How to solve a 2nd order non-homogeneous linear recurrence?

I have a problem in solving this equation : $x_{n+2} + 3\ x_{n+1} + 2\ x_{n} = 5 \times 3^n $ given that $x_{0} = 0$ and $x_{1} = 1$. I solved the homogeneous associated equation and got $v_{n} = ...
6
votes
0answers
190 views

Coefficients in expansion of $(\sqrt[3]{2} - 1)^m$

In trying to solve $a^3 - 2b^3 = 1$ over the integers I came across the need to answer the question: when does $(1+ \sqrt[3]{2} + \sqrt[3]{2}^2)^n$ have no $\sqrt[3]{2}^2$ term in it's expansion (in ...
2
votes
1answer
113 views

The annihilator of $n(2^n)\sin({n\pi \over 2})$

I have to solve this problem: $y(n+2)-y(n)=n(2^n)\sin({n\pi \over 2})$ And I know the annihilator of $n(2^n) = (E-2)^2$, but I don't know how I should find the other part of the annihilator. ...
0
votes
2answers
59 views

representing a recursive difference equation of two variables into one variable equation

suppose the following recursive difference equation ($t$ is time): $$x_t = \frac{a}{1+a}x_{t-1} + \frac{1}{1+a}x_{t+1}$$ where $0<a<1$ is assumed and all values of $a$ at past times are ...
7
votes
3answers
131 views

Help me understanding logic behind limits of recurence relations

I was trying to understand how limits of recurence relations are working. I have one. $$a_0 = \dfrac32 ,\ a_{n+1} = \frac{3}{4-a_n} $$ So, from what i know, if this recurence relation has a limit, ...
2
votes
3answers
126 views

Proof that $x^2 - 2y^2 = -1$ has a recurring solution for $x$

I read here about the following variation on Pell's equation: $$ x^2 - 2y^2 = -1.$$ According to Dario Alpern's solver, the equation has infinite integer ...
2
votes
1answer
60 views

What is the relationship between a non homogenous second order difference equation (constant coefficients) and its derivative?

Here's an excerpt of a lecture note I am reading (I've highlighted the beginning of the part that I don't understand): I don't understand how derivative comes into the picture. Here's some context ...
2
votes
1answer
117 views

Closed form solution to a recurrence relation (from a probability problem)

Is there a closed form solution to the following recurrence relation? $$P(i,j) = \frac{i^{5}}{5i(5i-1)(5i-2)(5i-3)(5i-4)}\sum\limits_{k=0}^{j-5}(1-P(i-1,k))$$ where $P(i,j)=0$ for $j<5$. The ...
0
votes
1answer
78 views

Recurrence relation question - check my answers! Basic questions.

I had a chat with a friend about these questions (they are homework questions) , and we argued about the solution. I would just like an outside opinion about my answers: 1) $n \geq 2$ people are ...
0
votes
1answer
145 views

Recurrence relation - simple question. Homework. Permutations with a twist,

I think I solved it but I would love someone to tell me if I'm wrong. the question is as follows: $n$ people are sitting on a bench with $n$ seats. Find a recursive equation that calculates how many ...
2
votes
1answer
93 views

Recurrence relations - simple questions, please verify my answers.

I'm posting this question because this is new material for me and I am unsure of my answers and have no one to consult with. I solved the first three and would appreciate feedback. I need help solving ...
6
votes
2answers
244 views

recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$

I've been trying to solve this recurrence relation for a week, but I haven't come up with a solution. $f(n)=5f(n/2)-6f(n/4) + n$ Solve this recurrence relation for $f(1)=2$ and $f(2)=1$ At first ...
0
votes
1answer
62 views

Recurrence relation that skips $n-1$?

A difficult question I'm having problems with regarding recurrence relations and recurrence equations. The question is as follows: In how many different ways can I cover a 3xn checkberboard with 2x1 ...
2
votes
1answer
47 views

Solving the recurrence $x_n = \frac{\sum_{i=0}^{n-1} x_i}{2n}$

In my answer over at cstheory.stackexchange.com I set variables according to the recurrence $$x_0=1, x_n = \frac{\sum_{i=0}^{n-1} x_i}{2n}$$ Wolfram Alpha tells me that apparently the solution to this ...
3
votes
5answers
120 views

Simple functional equation

I have a simple functional equation: $$ \alpha(x) = {1 \over 2}\left[\alpha\left(x - 1\right) + \alpha\left(x + 1\right)\right]\,, \qquad \alpha\left(0\right) = 1\,,\quad\alpha\left(m\right) = 0 $$ I ...
2
votes
1answer
104 views

How find this function $f(2^m)=?$

show that:there exists unique function $f:N^{+}\to N^{+}$,such $$f(1)=f(2)=1$$ and $$f(n)=f(f(n-1))+f(n-f(n-1))),n=3,4,\cdots$$ and Find $f(2^m),m>2,m\in N$ My try: let $n=3$ ,then we have ...
0
votes
3answers
402 views

Difficult recursion problem

A student can do the things bellow: a. Do his homework in 2 days b. Write a poem in 2 days c. Go on a trip for 2 days d. Study for exams for 1 day e. Play pc games for 1 day A schedule of n days ...
1
vote
1answer
293 views

Finding explicit formula for recurrence relation?

What would a explicit formula for this sequence? a_k = a_(k-1)/k? The way I find explicit formula is to write out some terms but this time it's not working.. I'd appreciate your help!
1
vote
2answers
117 views

What is the order of growth of the parameterized recurrence relation given below?

Given two parameters $a$ and $b$ (both positive integers), please estimate the order of growth of the following function: $$F(t)=\left\{\begin{array}{ll} 1, \, &t\le a \\ F(t-1) + b\cdot ...
3
votes
2answers
137 views

A proof using $\Delta^ny(t)=\sum_{k=0}^{n}{(-1)^k\dbinom{n}{k}y(t+n-k)}$

Please How can I use $\Delta^ny(t)=\sum_{k=0}^{n}{(-1)^k\dbinom{n}{k}y(t+n-k)}$ to prove $\sum_{i=0}^{n}{(-1)^i\dbinom{n}{i}y(i)}=(-1)^n\Delta^ny(0)$ and hence to evaluate ...
0
votes
1answer
146 views

Summation of falling factorials

I just want to know if I should evaluate $\sum(t+1)^\underline{4}$ the way we evaluate $\sum{t^\underline{4}}$. Thanks.
1
vote
1answer
240 views

Negative falling Factorial

Please can someone tell me what is the value of $1^\underline{-2}$? I know that $1^\underline{2}=0$. Thanks.
3
votes
2answers
65 views

Solve a recurrence relation

The sequence x is defined as follows: $x_{0} = 1, x_{t} =\sqrt{0.2x_{t-1}+0.9x_{t-1}^{2}}$ I want to know what is t when $x_{t} = 2$. I use a spreadsheet to calculate it. When t is 104, $x_{t} = 2$, ...
3
votes
1answer
59 views

Find the number of ways that 2n people may be paired.

Question: Find the number of ways that 2n people may be paired. I have figured this problem out, and I'm fairly certain that there are $\frac{(2n)!}{2^{n} n!}$ ways. However, I cannot seem to work ...
1
vote
1answer
154 views

Generating Function of a Recurrence Relation.

Given a sequence a(n) = a(n -2) , a(0) = 2 , a(1) = -1 Find the generating function What i have done so far: The recurrence relation is going to be a(n) - a(n-2) = 0 A = the generating function A ...
2
votes
3answers
81 views

Solve the recursion $a_{n} = n a_{n-1} + (n+1)!$

Define the sequence $\{a_{n}\}$ by $a_{n} = n a_{n-1} + (n+1)!$ for $n \geq 1$ and setting $a_{0} = 1$. Solve this recursion completely. I can solve this rather easily by an induction argument, where ...
0
votes
2answers
133 views

Prove (1 + x)^n + (1 - x)^n < 2^n by using Binomial Theorem

Hi my boss asked me to resolve this equation: Prove (1 + x)^n + (1 - x)^n < 2^n by using Binomial Theorem -1 < x < 1 ...
1
vote
2answers
81 views

Solving recurrence $T(n)=T(n-1)+3^{n-1}$

I have trouble solving following recurrence. $$T(n)=T(n-1)+3^{n-1}$$ So far I tried annihilators but it doesn't work.
0
votes
2answers
107 views

Repertoire Method. How to know when equations are valid

I'm trying to work a few examples from the Repertoire Method from the Book Concrete Mathematics. I'm working through the following recurrence: $f(0) = 1$ $f(n) = 2f(n-1) + n$ Which I generalized ...
2
votes
2answers
107 views

proof with recurrence relation

How can we proof that number ternary strings that do not contain two consecutive 0s or 1s is $a_n = 2a_{n-1} + a_{n-2}$ What I tried so far: Let $a_n$ be the number ternary strings that do not ...
1
vote
1answer
69 views

recurrence relation related problems

I'm having some difficulties of finding the recurrence relations of; number of divisions of internal region of n sided polygon number of paths from one point to another point in an NxN grid Can ...
0
votes
1answer
53 views

What's the maths symbol for alternation of product and sums?

Is there a mathematics symbol for referring to the equation below? (((((((((((100*y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x = 0, x = 9.8 I've tried using capital ...
3
votes
1answer
61 views

Equivalent of a recurrence sequence [duplicate]

Let $x_{0} = 2$ and $x_{n+1} = x_{n} + \ln(x_{n})$, how can I find an asymptotic equivalent of this sequence say, to the third term? (This is not homework, it was a problem in the Oral Examination ...
3
votes
1answer
1k views

Recurrence relation question

A country uses as currency coins with values of 1 peso, 2pesos, 5 pesos, and 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. a) Find a recurrence relation for ...
2
votes
1answer
1k views

Recurrence relations question

A vending machine dispensing books of stamps accepts only one-dollar coins, $1 bills, and $5 bills. a) Find a recurrence relation for the number of ways to deposit $n$ dollars in the vending machine, ...