Tag Info

Hot answers tagged

3

To show that $r_n = 3\cdot 2^n - 4\cdot 5^n$ satisfy the equation then start by writing the equation as $$r_n - 7r_{n-1} + 10r_{n-2} = 0$$ Now calculate $r_n, r_{n-1}$ and $r_{n-2}$ from the formula. This gives us $$r_n = \color{red}{3\cdot 2^n - 4\cdot 5^n}$$ $$r_{n-1} = 3\cdot 2^{n-1} - 4\cdot 5^{n-1} = \color{blue}{\frac{3}{2}\cdot 2^{n} - ...


2

$$7r_{n-1}-10r_{n-2}=7(3.2^{n-1}-4.5^{n-1})-10(3.2^{n-2}-4.5^{n-2})$$ $$7r_{n-1}-10r_{n-2}=(42-30).2^{n-2}+(-140+2=40)5^{n-2}$$ $$7r_{n-1}-10r_{n-2}=3.2^n-4.5^n$$ $$7r_{n-1}-10r_{n-2}=r_n$$


2

Wolfram Alpha gives the roots as $-1$ and $1/6 (3\pm i \sqrt(3))$. This last is $\frac{1\pm i\sqrt{1/3}}{2}$ which is your answer. My guess is either you misread WA's answer or you entered the equation incorrectly.


2

i am going to try. the defining relation for $f$ gives us the inequality $$nf(n) = n\{f(f(n-1)) + 1\} =n + nf(f(n-1)) \ge n $$ because the range of $f$ consists of positive integers. we can use $jf(j) \ge j$ again and again to get $$ nf(n) \ge n + nf(f(n-1)) \ge n + nf(n-1) \ge n + n(n-1) = n^2$$ therefore $$1f(1) + 2f(2) + \cdots + nf(n) \ge 1^2 + 2^2 + ...


2

If $f(x)=f(y)$ then $f(x+1)=f(f(x))+1=f(f(y))+1=f(y+1)$, so $f(n)$ is periodic. But every number $f(m)$ in the cycle is one more than another number in the cycle. This is a contradiction, so $f(x)\neq f(y)$ when $x\neq y$. $f(n+1)=f(f(n))+1>f(f(n))$, so $f(n+1)$ is never the lowest value that $f(x)$ takes. So $f(1)$ must be the lowest value that $f(x)$ ...


2

When we have given an linear recurrence equation of a sequence such as your case : $$y(n+2)+2y(n+1)-3y(n) = -2n$$ The first point is to find the general solution of the associated homogeneous equation $$\tilde{y}(n+2)+2\tilde{y}(n+1)-3\tilde{y}(n) = 0$$ which you did $\tilde{y}(n) = c_1(-3)^n+c_2$. (the general method consist to solve the associated ...


1

I can compute $DP[i][j][k]$ in $O(N^2)$. To see this, note that the first term of the summation ($DP[i][m][0]$) can always be computed in $O(1)$, and the second term of the second term of the summation ($j$ from $DP[m+1][j][k-1]$)... is always $j$. ...assuming everything is memoized, of course.


1

Pick d) as an example. You are given $a_0 = -1, a_1 = 0$. The recurrence formula is $a_n = n a_{n-1} + a_{n-2}^2$, so setting $n=2$ gives $a_2 = 2 a_1 + a_0^2$, and evaluating gives $a_2 = 1$. Repeating for $n=3$ gives $a_3 = 3 a_2 + a_1^2$ and evaluating gives $a_3 = 3$. Etc, etc.


1

A general first order recurrence relation $$ a_{n+1} - f_n a_n = g_n \longrightarrow (1). $$ admits the following solution $$ a_n = \left(\prod_{k=0}^{n-1} f_k \right) \left(a_0 + \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}\right). $$


1

let $$\dfrac{h_{n-1}}{h_{n}}=(1+cq^{n-1})p$$ so we have $$\dfrac{h_{n-2}}{h_{n-1}}=(1+cq^{n-2})p$$ $$\cdots\cdots$$ $$\dfrac{h_{1}}{h_{2}}=(1+cq)p$$ $$\dfrac{h_{1}}{h_{n}}=\prod_{k=1}^{n-1}(1+cq^k)p\Longrightarrow h_{n}=\dfrac{h_{1}}{\prod_{k=1}^{n-1}(1+cq^k)p}$$ then we have $$t_{n}=\dfrac{h_{n-1}}{h_{n}}t_{n-1}+an+b$$ $$\Longrightarrow ...


1

Since $1\cdot 1+ 2\cdot 2+ \cdots + n\cdot n = n(n+1)(2n+1)/6$, it is enough to prove that $f(n)\le n$, for all $n$. We shall prove that $f(n)\le n$ for all $n$, by full induction. Assume $f(m)\le m$ for all $m\le n$. Let's prove that $f(n+1) \le n+1$. Let $m=f(n) \le n$. Then $f(f(n))=f(m) \le m=f(n)$. So, $f(n+1) = f(f(n))+1 \le f(n)+1 \le n+1$. All ...


1

For the first, no, because $F_n \approx \phi^n/\sqrt{5}$ where $\phi =\dfrac{1+\sqrt{5}}{2} \approx 1.618 $. For the second, yes, eventually for any $k > 0$ for the reason given above.


1

After correcting the typos, we have $$\begin{align*} A(z)&=2+z\sum_{n\ge 1}a_{n-1}z^{n-1}+z\sum_{n\ge 1}2^{n-1}z^{n-1}\\ &=2+z\sum_{n\ge 0}a_nz^n+z\sum_{n\ge 0}2^nz^n\\ &=2+zA(z)+z\sum_{n\ge 0}2^nz^n\;, \end{align*}$$ since $A(z)=\sum_{n\ge 0}a_nz^n$. Now just subtract $zA(z)$ from both sides to get $$(1-z)A(z)=A(z)-zA(z)=2+z\sum_{n\ge ...


1

With Abhishek Bakshi hint ,Now I have complete this answer, since $$\dfrac{a_{n}}{n!}=\dfrac{1}{2}\dfrac{a_{n-1}}{(n-1)!}+\dfrac{1}{2}\dfrac{a_{n-2}}{(n-2)!}+\dfrac{(-)^n(1-\dfrac{n}{2})}{n!}$$ let $b_{n}=\dfrac{a_{n}}{n!},b_{1}=0,,b_{2}=\dfrac{1}{2} $then we have $$b_{n}=\dfrac{1}{2}b_{n-1}+\dfrac{1}{2}b_{n-2}+\dfrac{(-)^n(1-\dfrac{n}{2})}{n!}$$ ...


1

How did you input the equation into Wolfram Alpha? You have as solutions $$ \begin{align} a_n&=(-1)^n\tag{1}\\[9pt] b_n &=\frac12\left[\,\left(\frac{1+\frac i{\sqrt{3}}}{2}\right)^n+\left(\frac{1-\frac i{\sqrt{3}}}{2}\right)^n\,\right]\\ &=\mathrm{Re}\left[\,\left(\frac{1+\frac i{\sqrt{3}}}{2}\right)^n\,\right]\tag{2}\\[9pt] c_n ...



Only top voted, non community-wiki answers of a minimum length are eligible