Can my approach for this 'verification by Induction' be simplified?

72 Views Asked by At

Sorry:

I don't know math scripting, so arguments maybe clumsy, sorry.

Problem (let's take sub-question (c) for simplicity)

problem pic

So, the problem is:
Given: a1 = 1 and an+1 = ((2n + 1)/(n+1)).an for all n >= 1
To find (and verify its truth by Induction): an

My approach:

Let Pn:
(definition for an I'm assuming to be true)
an = 1, if n = 1
OR
an = ((2n-1)/n).an-1, if n > 1

Note: The style given: am and an: am means value of am obtained by given definition (a1 = 1 or formula for an+1) and an definition (the one I assumed to be true).

P1:
given: a1 = 1
an: a1 = 1
given: a1 = an: a1 => P1 is true

Now assume Pn is true:
Case 1: n = 1
an: a1 = 1
an: a2 = ((2(2)-1)/2).a2-1 = 3/2
given: a2 = ((2(1)+1)/(1+1)).a1 = (3/2).a1
substituting an: a1 here,
given: a2 = (3/2)
here an: a2 == given: a2
=> P1 implies P2 --- (1)

case 2: n > 1
an: an = ((2n-1)/n).an-1
an: an+1 = ((2(n+1)-1)/(n+1)).a(n+1)-1 = ((2n+1)/(n+1)).an
given: an+1 = ((2n+1)/(n+1)).an
here an: an+1 = given: an+1
=> Pn implies Pn+1 --- (2)

(1) and (2) => Pn => Pn+1 for all n >= 1,therefore, Pn is true for all n >= 1

So, the definition of an is
an = 1, if n = 1
OR
an = ((2n-1)/n).an-1, if n > 1

question:

  1. Is my approach correct?
  2. Is there any simpler approach?

EDIT 1: Clarification

my question's solution is No, my approach is wrong, I need to find an explicit formula for an.

This may be the context you need to understand my question clearly :
My assumed formula for an was not an "Explicit" formula; I didn't know what it means. I transformed the given formula by replacing n with n-1 to get a formula for a_n (of the form an = f(an-1)) and thought I need to prove this transformed definition is true using induction principle, and that's what I did here. Thanks to @coffeemath for explaining what "Explicit formula" means.

1

There are 1 best solutions below

4
On

I note you are asking only about problem 9 part (c) in which $$a_1=1,\ \ a_{n+1}=\frac{2n+1}{n+1}a_n.\tag{1}$$ I found that an explicit formula is given by $$a_n = \frac{\binom{2n}{n}}{2^n}.$$ Here the numerator is the central binomial coefficient, and the formula may be established by induction using the factorial version of the binomial coefficient, i.e. $(2n)!/(n!)^2.$ The algebra for the induction step is left for you; it is fairly straightforward using some simple properties of factorials.

added: This same recurrence and formula is associated with the Taylor series of $1/\sqrt{1-2x}$ centered at $0$ whose general term is $a_nx^{n-1}, n \ge 1.$