Intereting Posts

Reference request: calculus of variations
Prove that $\int_0^\pi\frac{\cos x \cos 4x}{(2-\cos x)^2}dx=\frac{\pi}{9} (2160 – 1247\sqrt{3})$
Find closed form for $a_{1}=2, a_{n}=a_{n-1}+n+6$
Ring of formal power series over a principal ideal domain is a unique factorisation domain
If $\sum a_n$ is a convergent series with $S = \lim s_n$, where $s_n$ is the nth partial sum, then $\lim_{n \to \infty} \frac{s_1+…+s_n}{n} = S$
How to find the vertices angle after rotation
Time for the tank to be empty
Second derivative of class $C^2$ expressed as limit
Proof by induction that $B\cup (\bigcap_{i=1}^n A_i)=\bigcap_{i=1}^n (B\cup A_i)$
What is circumradius $R$ of the great disnub dirhombidodecahedron, or Skilling's figure?
Topological vector spaces vs. locally convex spaces
Underdetermined linear systems least squares
The number of divisors of any positive number $n$ is $\le 2\sqrt{n}$
What to do with an empty column in the basis of the null space?
Find all positive integers $n$ such that $n+2008$ divides $n^2 + 2008$ and $n+2009$ divides $n^2 + 2009$

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$.

- Is there a formula for finding the number of nonisomorphic simple graphs that have n nodes?
- The asymptotic behaviour of $\sum_{k=1}^{n} k \log k$.
- Number of permutations of a specific cycle decomposition
- How many combinations can be made from this scenario?
- Sitting in chairs with empty space
- Showing that a root $x_0$ of a polynomial is bounded by $|x_0|<(n+1)\cdot c_{\rm max}/c_1$

We want to calculate order of T.

I’m confused by using recursion tree and some maths induction.

- How much weight is on each person in a human pyramid?
- Proving Set Operations
- How many combinations can I make?
- isomorphism $\Bbb Q$ to $\Bbb Q \cap (0,1)$
- Divisibility of prime numbers
- Construction of uncountably many non-isomorphic linear (total) orderings of natural numbers
- Is there a number that is palindromal in both base 2 and base 3?
- Diffucult Tautology to Prove
- Free resources to start learning Discrete Mathematics
- Are the Hyperreals complete?

Starting with:

$$

T(n) = n + \sum_{k=1}^{n-1} \left[T(n-k) + T(k)\right]

$$

The two terms in the square braces are the same; one is counting down and the other counting up, so:

$$

T(n) = n + 2\times \sum_{k=1}^{n-1} T(k)

$$

To find the order of $T$, we need to compare $T(n)$ to $T(n-1)$.

$$

T(n-1) = (n-1) + 2\times \sum_{k=1}^{n-2} T(k)

$$

So we rearrange terms in the definition of $T(n)$:

$$

\begin{align}

T(n) &= [(n-1) + 1] + 2\times \left[ \left(\sum_{k=1}^{n-2} T(k)\right) + T(n-1)\right]\\

&= 1 + \left[(n-1) + 2\times \left(\sum_{k=1}^{n-2} T(k)\right)\right] + 2\times T(n-1)\\

&=1 + T(n-1) + 2\times T(n-1)\\

&= 3\times T(n-1) + 1

\end{align}

$$

Thus, $T(n)$ is $O(3^n)$. Given that $T(1) = 1$, we see $T(n) = 3^n/2-1/2$.

Use generating functions. Define $g(z) = \sum_{n \ge 0} T(n + 1) z^n$, write yout recurrence as:

$$

T(n + 2)= n + 2 + 2 \sum_{1 \le k \le n + 1} T(n)

$$

Multiply by $z^n$, sum over $n \ge 0$ and recognize the resulting sums:

$$

\frac{g(z) – T(1)}{z}

+ z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 – z} + \frac{2}{1 – z}

+ 2 \frac{g(z)}{1 – z}

$$

go get, written in partial fractions:

$$

g(z) = \frac{3}{2} \cdot \frac{1}{1 – 3 z} – \frac{1}{2} \cdot \frac{1}{1 – 2 z}

$$

Thus:

$$

T(n) = \frac{3^n}{2} – 2^{n – 2}

$$

- Does a continuous and 1-1 function map Borel sets to Borel sets?
- How to analyze the time complexity $\Theta$ of this recurrence
- a non-monotonic function on with infinitely many points of discontinuity such that the function is bounded & Riemann integrable on .
- How prove this$\frac{1}{P_{0}P_{1}}+\frac{1}{P_{0}P_{2}}+\cdots+\frac{1}{P_{0}P_{n}}<\sqrt{15n}$
- Different types of domains $\Omega \subset \mathbb{R}^n$ in PDEs
- When is a sum of consecutive squares equal to a square?
- Lebesgue Measure of the Graph of a Function
- Tight bounds for Bowers array notation
- Closed form for $\sum_{n=1}^{\infty}\frac{1}{\sinh^2\!\pi n}$ conjectured
- Non-integer powers of negative numbers
- Projection of ellipsoid
- How do I find $\lim\limits_{x \to 0} x\cot(6x) $ without using L'hopitals rule?
- Why has the Perfect cuboid problem not been solved yet?
- Can every nonsingular $n\times n$ matrix with real entries be made singular by changing exactly one entry?
- On the completeness of the generalized Laguerre polynomials