Proof by Induction | Mathematics | Page 1

craggy chasm Oct 20, 2024, 9:40 AM

#

I have to that this equation is true for all positive integers including zero
The second picture shows at what point i am stuck on currently.
Thanks in advance!

upbeat gazelleBOT Oct 20, 2024, 9:40 AM

#

craggy chasm I have to that this equation is true for all positive integers including zero Th...

#

Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
Wait patiently for a helper to come along.
Once someone helps you, say thank you and close the thread with:
```
+close
```
Feel free to nominate the person for helper of the week in #helper-nominations
Do not ping the mods, unless someone is breaking the rules. If there is a conflict amongst multiple helpers feel free to ping “Helper Mod”
If you're happy with the help you got here, and the server overall, you can contribute financially as well:

wide ether Oct 20, 2024, 12:46 PM

#

craggy chasm I have to that this equation is true for all positive integers including zero Th...

hello, I think that you should avoid at all cost to expand the binomials as a sum

#

the easiest way, in my opinion, would be to rather compute the quotient (2n+2 n+1) / (-1/2 n+1), expand using the formula for binomial coefficients involving factorials to make appear the factor (2n n) / (-1/2 n) (equal to 1 by induction hypothesis), and then to just show that the remaining factor is equal to one

#

another way would be to compute separately (2n+2 n+1) / (2n n) = un (a fraction of n), and (-1/2 n+1) / (-1/2 n) = un

#

this way, as they are the same at n=0, you can conclude with an easy induction

craggy chasm Oct 20, 2024, 2:27 PM

#

Sorry. Might be a language problem because im not used to speak about maths in english but can you try to explain it again pls @wide ether 😓
But thank you that you showed me a mistake in the beginning of my induction

proud gardenBOT Oct 20, 2024, 2:27 PM

#

@craggy chasm has given 1 rep to @wide ether

wide ether Oct 20, 2024, 2:29 PM

#

(so my notation is (n k) for nCk, I find it more readable)

#

ok, what is (2n+2 n+1) / (2n n) ?

craggy chasm Oct 20, 2024, 2:42 PM

#

wide ether ok, what is (2n+2 n+1) / (2n n) ?

Something like this

wide ether Oct 20, 2024, 2:44 PM

#

write it without factorials

#

(you can simplify your expression further)

#

for instance, you can rewrite (2n+2)! as (2n+2) (2n+1) (2n)!

craggy chasm Oct 20, 2024, 2:45 PM

#

2 * (2n+1) / (n+2)

wide ether Oct 20, 2024, 2:45 PM

#

craggy chasm Something like this

wait, be careful, it is (2n+2 n**+1**) and not (2n+2 n+2)

craggy chasm Oct 20, 2024, 2:45 PM

#

oh oops

craggy chasm Oct 20, 2024, 2:50 PM

#

wide ether wait, be careful, it is (2n+2 n**+1**) and not (2n+2 n+2)

2 * (2n+1)/(n+1)

wide ether Oct 20, 2024, 2:51 PM

#

yes

#

now, do the same thing with (-4)^(n+1) (-1/2 (n+1)) / ( (-4)^n (-1/2 n))

#

you should obtain the same fraction in the end

craggy chasm Oct 20, 2024, 2:52 PM

#

Okay let me calculate rq

#

Ok i suck at calculating it @wide ether
How do i use the binomial coefficient properly with negative x

wide ether Oct 20, 2024, 3:03 PM

#

so, the definition of (x k) for any x and positive integer k is x(x-1)…(x-k+1) / k!

#

thus you have that (x (k+1)) = (x-k) / (k+1) × (x k)

craggy chasm Oct 20, 2024, 3:09 PM

#

in the end i got

#

2* ( 2n+1) / (n+1)

craggy chasm Oct 20, 2024, 3:10 PM

#

craggy chasm 2 * (2n+1)/(n+1)

so exactly this again

wide ether Oct 20, 2024, 3:10 PM

#

yes

#

I think that it should not be too hard to perform the induction after seeing this

craggy chasm Oct 20, 2024, 3:11 PM

#

Actually i don't understand what information i got out of this

wide ether Oct 20, 2024, 3:12 PM

#

you have that the sequences (2n n) and (-4)^n (-1/2 n) both satisfy the recurrence relation u(n+1) = 2 (2n+1)/(n+1) u(n) with u(0) = 1

#

so they must be equal

#

because the solution to such a recurrence relation is unique

#

you can prove it by induction

craggy chasm Oct 20, 2024, 3:13 PM

#

So you wanted me to bring the problem down to a simpler induction problem?

wide ether Oct 20, 2024, 3:13 PM

#

yes

#

but it also helps in your original setting

#

if you assume that (2n n) = (-4)^n (-1/2 n), then by your result you have that
(2n+2 n+1) = 2 (2n+1)/(n+1) (2n n)
= 2 (2n+1)/(n+1) (-4)^n (-1/2 n) by induction hypothesis
= (-4)^(n+1) (-1/2 (n+1))

#

and here goes your induction step

#

it is still interesting to know this pattern : two sequences which satisfy the same induction scheme and initial conditions must be equal

craggy chasm Oct 20, 2024, 3:16 PM

#

Okay i will think about what you said. Is it okay if i text later again?

wide ether Oct 20, 2024, 3:16 PM

#

yes, in this channel

craggy chasm Oct 20, 2024, 4:38 PM

#

wide ether yes, in this channel

Okay I think that I understood your method. Without you i wouldn't have solved this problem so thanks a lot!

proud gardenBOT Oct 20, 2024, 4:38 PM

#

@craggy chasm has given 1 rep to @wide ether

wide ether Oct 20, 2024, 4:39 PM

#

you're welcome

#

+close

craggy chasm Oct 20, 2024, 4:40 PM

#

Last question: I could have solved this problem without induction right?

wide ether Oct 20, 2024, 4:40 PM

#

yes

#

you could just have expanded (-4)^n (-1/2 n) as a product and distributed cleverly the (-4)^n among the factors of the numerator

craggy chasm Oct 20, 2024, 4:41 PM

#

I understand. Thanks. Have a nice evening!

#

+close

#Proof by Induction