# Proof by induction

1. Oct 1, 2009

### IHateMayonnaise

1. The problem statement, all variables and given/known data

Given the definition of the spherical Bessel function,

$$j_{\ell}(\rho)=(-\rho)^{\ell} \left(\frac{1}{\rho}\frac{d}{d\rho}\right)\frac{Sin{\rho}}{\rho}$$

Prove the recurrence relation:

$$j_{\ell+1}(\rho)=-j_{\ell}^{'}(\rho)+\frac{\ell}{\rho}j_{\ell}(\rho)$$

2. Relevant equations

[See a]

3. The attempt at a solution

The method to prove the recursion relation should be completed using proof by induction. This really comes down to the formalities involved in completing a proof of this nature: proof by induction implies that if the to-be-proved relation holds for one value (say, $k$) then it may be induced that it holds for subsequent values ($k+1$). My question: must I demonstrate that the relation holds for any arbitrary $k$, or can I just pick one (say, 1) and then show that the relation holds for what you would expect from the original equation (for 1+1=2)?

Thanks
IHateMayonnaise

Last edited: Oct 1, 2009
2. Oct 1, 2009

### LCKurtz

You have to do two things:
1. Show it is true for your starting value of k, usually, but not always, k = 1. Sometimes you may need to start with the first 2 values of k.

2. Then show that if it is true for any given k, then it is true for the next k. This part of the argument must work for arbitrary k. You can't just pick one.

3. Oct 1, 2009

### IHateMayonnaise

So: what you're saying is that after I show that it is true for some value (say, k=1), then I must show that the relation is true for any k by putting k into the second equation and showing that it is the same as putting k+1 in the first equation?

4. Oct 1, 2009

### LCKurtz

No, that isn't quite it. Let's call the proposition that you are trying to prove for all natural numbers k by the name P(k). The first step is to show P(1) is true.

For the induction step, you assume P(k) is true. You don't have to prove it; it is a given. The work is in showing that you can get from there to show P(k+1) is true.

Think of the analogy of climbing a ladder. You would have to do two things:

1. Get on the first rung. (Show it isn't too high off the ground or some other problem).
2. No matter what rung you are on, you need to be able to get to the next rung. (No rung is too far from the previous to reach or is broken etc.).

5. Oct 2, 2009

### IHateMayonnaise

That mostly makes sense, thanks for your replies. But if I wanted to prove that l+1 is true (assuming that l is true) then all I would do is put l+1 into the first equation and play with it until it is the same as the second equation?

6. Oct 2, 2009

### LCKurtz

You want to prove P(k+1) is true given that P(k) is true. What makes induction arguments difficult is that there is no rule for this step. You have to do whatever it takes to work with P(k) to get P(k+1). For simple series type problems sometimes it is as simple as adding the next term and simplifying things. Sometimes you have to multiply P(k) by just the right thing and factor or use an inequality. Or it might be an entirely geometric argument having to do with the number of sides of a polygon. There are simply no rules; it depends on the problem.

Often, a good way to start is to write down P(k) as given. Then write down to prove: P(k+1). Then look at the information you have about the problem and see how you can manipulate or use P(k) to obtain P(k+1).