Tagged Questions

17 views

Concrete math generalized josephus recursion understanding 1.15

I am studying through the josephus problem in concrete math , Here is the equation of binary form $$f(1) = α ;$$ $$f(2n + j) = 2f(n) + β_j ,$$ $$\text{ for } j = 0, 1 \text{ and } n \geq 1$$ this ...
32 views

How to solve a non-homogeneous second-order linear difference equation with both a forward and a backward difference?

Quite a long title for this: I'm looking for the general solution of the following difference equation: $$ax_{t+1} -bx_t + x_{t-1} = c + u_t$$ where $a,b,c$ are real constants and $u_t$ is a bounded ...
60 views

Solving this recurrence relation

please tell me a way to solve this recurrence $$n\cdot R_n=C_1\cdot R_{n-1}+C_2\cdot R_{n-2}.$$ $C_1$ and $C_2$ are constants.. There is an $n$ there in the left hand side.. it makes mess. I tried ...
23 views

124 views

Recurrence Relation Solving Problem

Can anyone help me in solving this complex recurrence in detail? $T(n)=n + \sum\limits_{k-1}^n [T(n-k)+T(k)]$ $T(1) = 1$. We want to calculate order of T. I'm confused by using recursion tree ...
37 views

Divide and Conquer Recurrence Relation help?

So the divide and concur recurrence has to be of the form H($n$) = $a$H($n$/$b$) + $cn^d$. I already figured out that $a$ = 4 and $b$ = 2. I am really stuck on how to find $cn^d$ however. I ...
24 views

Particular solution of recurrence relation

I've got this recurrence relation: $$M_n = M_{n-1} + n(2n-1)|M_0 = 0$$ and can't think of any form of particular solution to get a solvable constant. With $M_n^H = K$being the homogeneous part of ...
172 views

Show that $2^n(\cos^n(\frac{2\pi}{9})+\cos^n(\frac{4\pi}{9})+\cos^n(\frac{8\pi}{9}))\in\mathbb{Z}$

$a_n=2^n\left[\cos^n\left(\dfrac{2\pi}{9}\right)+\cos^n\left(\dfrac{4\pi}{9}\right)+\cos^n\left(\dfrac{8\pi}{9}\right)\right]$. Show that $a_n\in\mathbb{Z}$ for all $n\in\mathbb{Z}$. Find the last ...
35 views

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 ...
89 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 ...
73 views

Need help with recurrence relation

So the question is: "Find a recurrence relation for the number of ways to pick $n$ objects from $k$ types with at most 3 of any one type" I think I figured out what it would be excluding the last ...
119 views

find the recurrence relation (homework)

I'm new to recurrence relations and I'm having trouble figuring out this problem: Find a recurrence relation for the number of ways to make a stack of green, yellow, and orange napkins so that no two ...
28 views

23 views

proving a recurrence relation

I'm trying to prove that the recurrence $T(n) = T(\alpha n)+T((1-\alpha)n)+n$, where $0<\alpha<\frac{1}{2}$, has an order of growth $T(n)= an$ log $n$ $\in \Theta(nlog(n))$ where $a$ is a ...
33 views

Solve recurrence $a[n,k]=(2m-2k)\;a[n-1,k+1]+k\;a[n-1,k]$

I'm trying to count how many vectors of size $n$ there are, given that the elements of the vector are integers from the range $\{-m,m\}-\{0\}$ (zero is excluded), and there are no pair of elements ...
40 views

Find a recurrence for in , the number of integer compositions of n which only have 1s and 2s as parts.

Find a recurrence for $$i_n$$ the number of integer compositions of $n$ which only have $1$s and $2$s as parts. How do you approach this problem?
35 views

Finding general solution to a non-linear discrete time recurrence relation

I am faced to a non-linear discrete time reccurence relation and I can't find the general solution. The first question is: Is there a general recipe for finding the general solution to non-linear ...
82 views

Is there a closed-form solution to this recurrence?

A friend and I were examining polynomials of the form $p_n (x) = x (x+1) (x+2) \cdots (x+n -1)$ and we were trying to come up with some kind of closed form for the coefficients when the polynomial is ...
29 views

Finding the recurrence relation? [duplicate]

If I let $n \geq 1$ be an integer and use a $2 \times n$ board $D_n$ containing $2n$ cells, each side has a length of 1. T The brick can be vetical or horizontal containg $2$ cells(explained in the ...