Verifying a Recursion Formula

95 Views Asked by At

enter image description here

I am attempting to prove the equation at the bottom of the image, or simply verify that it is a true mathematical relationship. I have computed a(3) and, in the latter part of the question, found the base case for using induction. (Note: I am only allowed to use inductive reasoning to prove this.)

2

There are 2 best solutions below

3
On BEST ANSWER

I'm not sure what your background is, so I will try to be thorough in my description of what is happening. Know that I'm not trying to be patronizing at all, I just want to make sure that everything I say is clear.

First the question defines a sequence of real numbers $a_0, a_1, a_2, a_3, \ldots$ by referring to terms which came before. The definition says:

$$a_0 = 1$$

$$a_n = r a_{n-1} + d$$

Let's compute a few terms of our sequence, then:

$a_0 = 1$ is given to us. So that one's easy to compute.

$a_1$ is a bit harder. We know that $a_1 = r * a_{1-1} + d$ from the second equation, and so we can simplify

$$a_1 = r * a_0 + d = r * 1 + d = r+d$$

we are able to do this because we already know $a_0$!

Similarly, we can compute $a_2$ as follows:

$$a_2 = r * a_{2-1} + d = r * a_1 + d = r * (r + d) + d = r^2 + rd + d$$

so $a_2 = r^2 + rd + d$

Again, we are only able to do this because we already know $a_1$.

At this point, you should be equipped to solve the first part of the problem:

$$\text{compute $a_3$}$$

You know $a_2$, so by following the above pattern, you should be able to compute $a_3$ for yourself.


It's clear that, continuing in this manner, we can find $a_{17}$ eventually. Or $a_{150}$, or any $a_n$ we want. What is equally clear is that this process will take a very long time. Even if we get a computer to do it, this is a tedious process for large $n$. It's natural, then, to ask if there's a better way. Is there some formula which will just tell us $a_n$ without us having to compute $a_{n-1}$, which requires us to compute $a_{n-2}$, which requires us to compute $a_{n-3}$ and so on?

The problem is kind enough to tell us what $a_n$ is equal to. Instead of going through this exhausting process of building our way up from $a_0$, we can just plug $n$ into a formula:

$$a_n = r^n + \frac{1-r^n}{1-r}d$$

Let's check this on some small cases.

We know $a_0$ should be $1$. Let's check the formula:

$$a_0 = r^0 + \frac{1-r^0}{1-r}d = 1 + \frac{0}{1-r}d = 1$$

It works! What about $a_1$? Again, from the previous discussion we know it should be $r+d$. What does the formula give?

$$a_1 = r^1 + \frac{1-r^1}{1-r}d = r + d$$

So far so good! Let's do $a_2$ together as well. We know it should be $r^2 + rd + d$. Indeed...

$$a_2 = r^2 + \frac{1-r^2}{1-r}d = r^2 + \frac{(1+r)(1-r)}{1-r}d = r^2 + (1+r)d = r^2 + rd + r$$

The formula seems to work! Now you can check your answer from before. You computed $a_3$ directly - does your answer agree with the answer the formula gives?


Of course, checking that the formula works for $n=0,1,2,3$ isn't enough to know that the formula works. We want to prove (with induction) that the formula always gives the same value as $a_n$.

Well, we can start with the base case: $a_0 = 1$, and the formula agrees!

Now let's do the inductive case. Say we know that $a_{n-1} = r^{n-1} + \frac{1 - r^{n-1}}{1-r}d$. Can we show that $a_n = r^n + \frac{1-r^n}{1-r}d$?

Well, let's see:

$$a_n = r a_{n-1} + d$$

thankfully we have an expression for $a_{n-1}$ lying around (this is our Inductive Hypothesis): let's substitute it in.

$$a_n = r (r^{n-1} + \frac{1-r^{n-1}}{1-r}d) + d$$

We can simplify this a little:

$$a_n = r^n + \frac{r (1-r^{n-1})}{1-r}d + d = r^n + \frac{r - r^n}{1-r}d + d$$

Now, ideally, we would be able to show that this expression is equal to $r^n + \frac{1-r^n}{1-r}d$. I'll leave it to you for now, but I suggest factoring out the $d$ in the first expression. From there it's some simple algebra to get it to look like what you want it to look like. Good luck!


I hope this helps ^_^

0
On

A small trick

Considering $$a_n = r\, a_{n-1} + d$$ let $a_n=b_n+k$ and replace $$b_n+k=r \, b_{n-1}+ r k +d$$

So, make $$k=rk +d \implies k=\frac d {1-r}$$ and you are left with the simple $$b_n=r \, b_{n-1} $$ When solved for $b_n$, go back to $a_n=b_n+\frac d {1-r}$