Proof by induction question. It's been rotting my brain. Question 50 (1 Viewer)

Qeru

Well-Known Member
Joined
Dec 30, 2020
Messages
368
Gender
Male
HSC
2021
Induction

(n+1)^5 + (n+1)^3 + 2(n+1)
= (n^5 + n^3 + 2n) + 4(n^4 + 2n^3 + 3n^2) + n^2 (n+1)^2 + 8n + 4
Damn beat me to it. The proof for why is divisble by 4:

n is even: let n=2k then the expression becomes:

n is odd: let n=2k+1 then the expression becomes:
 

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
Damn beat me to it. The proof for why is divisble by 4:

n is even: let n=2k then the expression becomes:

n is odd: let n=2k+1 then the expression becomes:
More simply, , and , as the product of two consecutive integers, must be even and so its square must be divisible by 4.
 

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
A much more efficient non-inductive proof:

















 

Paradoxica

-insert title here-
Joined
Jun 19, 2014
Messages
2,556
Location
Outside reality
Gender
Male
HSC
2016
Black Magic Proof:

Observe the following identity:



All coefficients of the binomial sum are multiples of 4, and all binomial coefficients are integers, so the RHS is divisible by 4, hence the LHS must also be divisible by 4.

 

Qeru

Well-Known Member
Joined
Dec 30, 2020
Messages
368
Gender
Male
HSC
2021
Black Magic Proof:

Observe the following identity:



All coefficients of the binomial sum are multiples of 4, and all binomial coefficients are integers, so the RHS is divisible by 4, hence the LHS must also be divisible by 4.

Wow just wow. Im interested on how thats derived?
 

Paradoxica

-insert title here-
Joined
Jun 19, 2014
Messages
2,556
Location
Outside reality
Gender
Male
HSC
2016
Wow just wow. Im interested on how thats derived?
use the greedy algorithm to successively eliminate the highest available power by subtracting the appropriately weighted binomial coefficient

this is a lot of expanding and algebra simplification so it's not that much nicer than splitting into cases and arguing carefully, but it doesn't require a lot of thinking so that is an advantage of this method

also this only works for polynomials
 

Paradoxica

-insert title here-
Joined
Jun 19, 2014
Messages
2,556
Location
Outside reality
Gender
Male
HSC
2016
actually there is a systematic way of doing this and it's basically the discrete version of the derivative

Define the forward difference operator Δf(n) = f(n+1)-f(n)

the binomial coefficients xCk are the monomial analogues of the continuous monomials x^k /k!

in the sense that Δ(xCk) = (xC[k-1]), much like how D(x^k /k!) = x^[k-1]/(k-1)!

so you can use this to "differentiate" any polynomial expression and obtain the first, second, third, etc. "derivatives"

now observe that in classical calculus that for any polynomial (of degree n) P(x), you can write the polynomial in the following form:

P(0)x⁰/0! + P'(0)x¹/1! + P''(0)x²/2! + P'''(0)x³/3! + ... + P^(n) (0) x^n/n! (this is just the maclaurin series of P(x))

The same thing is true in discrete calculus, that you just evaluate each difference at 0 to obtain the coefficients of the binomial coefficients.

So we proceed, first defining f(x) = x^5 + x^3 + 2x

Δf(x) = 5x⁴ + 10x³ + 13x² + 8x + 4

Δ²f(x) = 20x³ + 60x² + 76x + 36

Δ³f(x) = 60x² + 180x + 156

Δ⁴f(x) = 120x + 240

Δ⁵f(x) = 120

and notice that the constant terms of each of these are the same weights as i have from my previous answer.

change x to n to recover the problem (i kept it the same just to make the analogy clearer)
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top