A community for students.
Here's the question you clicked on:
 0 viewing
zmudz
 one year ago
Let \(f(m,1) = f(1,n) = 1\) for \(m \geq 1, n \geq 1,\) and let \(f(m,n) = f(m1,n) + f(m,n1) + f(m1,n1)\) for \(m > 1\) and \(n > 1.\) Also, let
\(S(n) = \sum_{a+b=n} f(a,b), \text{ for } a \geq 1, b \geq 1.\)
Note: The summation notation means to sum over all positive integers \(a,b\) such that \(a+b=n.\)
Given that
\(S(n+2) = pS(n+1) + qS(n) \text{ for all } n \geq 2,\)
for some constants p and q, find pq.
zmudz
 one year ago
Let \(f(m,1) = f(1,n) = 1\) for \(m \geq 1, n \geq 1,\) and let \(f(m,n) = f(m1,n) + f(m,n1) + f(m1,n1)\) for \(m > 1\) and \(n > 1.\) Also, let \(S(n) = \sum_{a+b=n} f(a,b), \text{ for } a \geq 1, b \geq 1.\) Note: The summation notation means to sum over all positive integers \(a,b\) such that \(a+b=n.\) Given that \(S(n+2) = pS(n+1) + qS(n) \text{ for all } n \geq 2,\) for some constants p and q, find pq.

This Question is Closed

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0I bet there's a neat solution that involves working through and possibly solving the first part with the doubleindex recurrence, but I'll admit I don't know how to work with those. Just working with the \(S(n)\) recurrence, I'm getting \(pq=2\).

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0The first thing I did was to identify the first few terms of \(S(k)\). For \(f(m,n)\), you get this neat table: \[\begin{array}{ccccccc} &m&1&2&3&4&5&\cdots\\ n&\\ \hline 1&&\color{red}1&\color{green}1&1&1&1&\cdots\\ 2&&\color{green}1&\color{blue}3&5&7&9&\cdots\\ 3&&1&5&13&25&31&\cdots\\ 4&&1&7&25&63&129&\cdots\\ 5&&1&9&41&129&258&\cdots\\ \vdots&&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{array}\] with the pattern being \(\color{red}{\text{red}}+\color{green}{\text{green}}+\color{green}{\text{green}}=\color{blue}{\text{blue}}\). \(S(k)\) is the sequence given by the sum of the \(\color{green}{\text{greens}}\).

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0So, we have the following recurrence: \[\begin{cases}S(2)=2\\S(3)=5\\S(k+2)=pS(k+1)+qS(k)&\text{for }k\ge2\end{cases}\] Denote the generating function of \(S(k)\) by \(\sigma(x)\), i.e. \(\sigma(x)=\sum\limits_{k\ge2}S(k)x^k\). You can solve for \(\sigma(x)\): \[\begin{align*} S(k+2)&=pS(k+1)+qS(k)\\[1ex] \sum_{k\ge2}S(k+2)x^k&=p\sum_{k\ge2}S(k+1)x^k+q\sum_{k\ge2}S(k)x^k\\[1ex] \frac{1}{x^2}\sum_{k\ge2}S(k+2)x^{k+2}&=\frac{p}{x}\sum_{k\ge2}S(k+1)x^{k+1}+q\sigma(x)\\[1ex] \frac{1}{x^2}\sum_{k\ge4}S(k)x^k&=\frac{p}{x}\sum_{k\ge3}S(k)x^k+q\sigma(x)\\[1ex] \frac{1}{x^2}\left(\sigma(x)S(2)x^2S(3)x^3\right)&=\frac{p}{x}\left(\sigma(x)S(2)x^2\right)+q\sigma(x)\\[1ex] \sigma(x)&=\frac{(2p5)x^32x^2}{qx^2+px1} \end{align*}\]

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Finding the Taylor series for \(\sigma(x)\) by hand seemed excruciating to me, so I used Mathematica to find the first few terms (about \(x=0\)): \[\sigma(x)=2x^2+5x^3+(5p+2q)x^4+(5p^2+5q+2pq)x^5+\mathcal{O}(x^6)\] So, you have \[\begin{cases}S(4)=12\\S(5)=29\end{cases}~~\implies~~\begin{cases}5p+2q=12\\5p^2+5q+2pq=29\end{cases}~~\implies~~\begin{cases}5p+2q=12\\12p+5q=29\end{cases}\]

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Maybe this is the intended approach... As soon as you can establish the first few terms of \(S(k)\), the first half of the problem seems like fluff.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Finding the Taylor series for \(\sigma(x)\) by hand seemed excruciating to me, so I used Mathematica to find the first few terms (about \(x=0\)): \[\sigma(x)=2x^2+5x^3+(5p+2q)x^4+(5p^2+5q+2pq)x^5+\mathcal{O}(x^6)\] So, you have \[\begin{cases}S(4)=12\\S(5)=29\end{cases}~~\implies~~\begin{cases}5p+2q=12\\5p^2+5q+2pq=29\end{cases}~~\implies~~\begin{cases}5p+2q=12\\12p+5q=29\end{cases}\]

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Also, using the GF is overkill. You can probably just solve this using the analogue of undetermined coefficients for difference equations.

Zarkon
 one year ago
Best ResponseYou've already chosen the best response.1\[S(n)=\frac{\sqrt{2}}{4}(1+\sqrt{2})^n\frac{\sqrt{2}}{4}(1\sqrt{2})n\]

Zarkon
 one year ago
Best ResponseYou've already chosen the best response.1my \(n\) on the end fell down ;) \[\Large S(n)=\frac{\sqrt{2}}{4}(1+\sqrt{2})^n\frac{\sqrt{2}}{4}(1\sqrt{2})^n\]
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.