zmudz
  • zmudz
Let \(f(m,1) = f(1,n) = 1\) for \(m \geq 1, n \geq 1,\) and let \(f(m,n) = f(m-1,n) + f(m,n-1) + f(m-1,n-1)\) 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.
Mathematics
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get our expert's

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this
and thousands of other questions.

zmudz
  • zmudz
Let \(f(m,1) = f(1,n) = 1\) for \(m \geq 1, n \geq 1,\) and let \(f(m,n) = f(m-1,n) + f(m,n-1) + f(m-1,n-1)\) 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.
Mathematics
jamiebookeater
  • jamiebookeater
See more answers at brainly.com
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this
and thousands of other questions

anonymous
  • anonymous
I bet there's a neat solution that involves working through and possibly solving the first part with the double-index 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
  • anonymous
The 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}{cc|ccccc} &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
  • anonymous
So, 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^2-S(3)x^3\right)&=\frac{p}{x}\left(\sigma(x)-S(2)x^2\right)+q\sigma(x)\\[1ex] \sigma(x)&=\frac{(2p-5)x^3-2x^2}{qx^2+px-1} \end{align*}\]

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

anonymous
  • anonymous
Finding 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
  • anonymous
Maybe 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
  • anonymous
Finding 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
  • anonymous
Also, using the GF is overkill. You can probably just solve this using the analogue of undetermined coefficients for difference equations.
Zarkon
  • Zarkon
\[S(n)=\frac{\sqrt{2}}{4}(1+\sqrt{2})^n-\frac{\sqrt{2}}{4}(1-\sqrt{2})n\]
Zarkon
  • Zarkon
my \(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\]

Looking for something else?

Not the answer you are looking for? Search for more explanations.