2

I am currently trying to learn advanced mathematics. So I'm currently reading 'The Art of Proof' by Matthias Beck and Ross Geoghegan.

I tried to solve one of the problems but I don't know if I'm actually close to an answer or not. The thing is I'm still trying to wrap my head around the second part of mathematical induction i.e the P(n) implies P(n+1) part.

So here's the problem and my attempt at a solution

Project 4.23 (Leibniz’s formula) Consider an operation denoted by $^\prime$ that is applied to symbols such as u, v, w. Assume that the operation $^\prime$ satisfies the following axioms:

$(u + v)^\prime = u^\prime + v^\prime \\ (uv)^\prime = uv^\prime + u^\prime v\\ (cu)^\prime = cu^\prime$

Define $w^{k}$ recursively by

(i) $w^{0} := w$

(ii) Assuming $w^{n}$ defined (where $n \in Z_{\ge0}$), define $w^{(n+1)} := {(w^{n})}^\prime$

Proof $(uv)^{k} = \sum_{m=0}^{k}\binom{k}{m}u^m v^{k-m}$

Solution

$P(k):(uv)^{k} = \sum_{m=0}^{k}\binom{k}{m}u^m v^{k-m}$

$P(1):$ base case - we use 1 (instead of 0) for the first derivative

$(uv)^{1}$ $= \sum_{m=0}^{1}\binom{1}{m}u^m v^{1-m}\\ = \binom{1}{0}u^0 v^{1-0} + \binom{1}{1}u^1 v^{1-1}\\ = u^0v^1 + v^1u^0\\ = uv^1 + v^1u - - (i)$

$P(n):$ Assumed defined

$(uv)^n = \sum_{m=0}^{n}\binom{n}{m}u^m v^{n-m}$

$P(n+1):$ to be proved

$(uv)^{n+1} = \sum_{m=0}^{n+1}\binom{n+1}{m}u^m v^{n+1-m}$

$(uv)^{n+1}$ $= \sum_{m=0}^{n+1}\binom{n+1}{m}u^m v^{n+1-m}\\ = \sum_{m=0}^{n}\binom{n}{m}u^m v^{n-m} + \binom{n+1}{n+1}u^{n+1} v^{n+1-({n+1})}\\ = \sum_{m=0}^{n}\binom{n}{m}u^m v^{n-m} + u^{n+1} v^0\\ = \sum_{m=0}^{n}\binom{n}{m}u^m v^{n-m} + (u^{n})^1 v\\ = (uv)^n + (u^{n})^1 v$

I know $u^{n}$ is already defined. I also think I could make same case for $(uv)^{n}$. But I don't have the rationale to make that jump.

All and any help will be appreciated. If you don't have time for typing mathjax syntax, just do it on piece of paper and post a snapshot. I'll do the work and post it here

Parousia
  • 121
  • Why don't you use $k=0$ as base case? It's easier, and you'll have to prove it for $k=0$ anyway, as an induction starting at $1$ won't cover that case. And in your induction step you start by using what you try to prove, which you shouldn't. But more importantly, your proof is missing words. It's impossible for me to derive what you were thinking from from what you wrote. – celtschk Apr 03 '17 at 07:23
  • Like I mentioned, I used 1 to mean the first derivative. Using 0 as the base case seem to me to be like rewriting the function without doing any actual differentiation. So I was implicitly making the argument that the base case is the first derivative. I have taken note of the words part. Thanks – Parousia Apr 03 '17 at 07:38
  • Yes, the proof for $k=0$ is trivial. Nevertheless, to have a complete proof, you have to prove it. And having done that, the induction step already cares about the case $k=1$, so there's no need to explicitly prove that as well. And there's nothing wrong with a proof step being trivial; after all, a proof is not an exercise in making things complicated, it only exists to demonstrate that the claim is true. If a part of the claim is trivial, then there's nothing wrong with it. And BTW, it's not that trivial, as you have to at least use the fact that ${0\choose 0}=1$. – celtschk Apr 03 '17 at 07:48
  • Thanks. I've done the proof for $k=0$. Now I have actually taken the idea of @dezdichado. I really shouldn't start with what I'm trying to prove. Thing now is I'm stuck in the expansions of the summation and binomial. Its all new to me. – Parousia Apr 03 '17 at 10:54
  • 2
    Possible duplicate of Prove that $(fg)^{(n)} = \sum_{k=0}^n \binom{n}{k}f^{(k)}(x)g^{(n-k)}(x)$ – Hans Lundmark Feb 07 '18 at 18:00

1 Answers1

0

The basic idea with induction is to use: $$(uv)^{n+1} = \dfrac{d}{dx}(uv)^n = \dfrac{d}{dx}\Big( \sum_{k=0}^n\binom{n}{k}u^k v^{n-k}\Big) = \sum_{k=0}^n\binom{n}{k}\dfrac{d}{dx}(u^kv^{n-k}) = ... $$

The rest is simply some algebraic manipulation using the fact that $\binom{n+1}{k} = \binom{n}{k}+\binom{n}{k-1}.$

dezdichado
  • 13,888
  • I'll try my hand using this idea then I'll report back. Might take me some time though. – Parousia Apr 03 '17 at 07:41
  • @Parousia, I intentionally left out the details, since you said you are actually trying to learn solving advanced problems. – dezdichado Apr 03 '17 at 07:47
  • I am currently here: $\sum_{m=0}^{n}\binom{n}{m}u^m (v^{n+1-m}) + \sum_{m=0}^{n}\binom{n}{m}(u^{m+1}) v^{n-m}$. Am I on the right track? The identity and expansion still confuses me though, but its ok. My main challenge is how to manipulate the $\sum$ sign as I navigate in and out of the bracket and between various intervals – Parousia Apr 03 '17 at 10:56
  • I've also done this $\sum_{m=0}^{n}\binom{n}{m}\frac{d}{dx}(u^m v^{n-m}) = \sum_{m=0}^{n}\binom{n+1}{m}\frac{d}{dx}(u^m v^{n-m}) - \sum_{m=0}^{n}\binom{n}{m-1}\frac{d}{dx}(u^m v^{n-m})\ \text{ and this}$ $\sum_{m=0}^{n}\binom{n}{m}(u^m (v^{n-m})^1 + (u^m)^1 v^{n-m}) = \sum_{m=0}^{n}\binom{n+1}{m}[(u^m (v^{n-m})^1 + (u^m)^1 v^{n-m})] - \sum_{m=0}^{n}\binom{n}{m-1}[(u^m (v^{n-m})^1 + (u^m)^1 v^{n-m})] = \sum_{m=0}^{n}\binom{n+1}{m}(u^m v^{n-m}) - \sum_{m=0}^{n}\binom{n}{m-1}(u^m v^{n-m})$ Going in so many directions. Maybe I'm overthinking this – Parousia Apr 03 '17 at 11:44
  • @Parousia actually here is an answer to the same question. So you were going in the right direction with your first step. In the future, make a quick search for your question in the site - most of beginning "advanced" math questions are already answered. – dezdichado Apr 03 '17 at 18:21
  • 10ks 4 ur help @dezdichado. Like I said in my qstn, d more I 'progress' wt ds question, the more I have to grapple with the fact that I don't have an idea where I'm heading. I don't know what I'm aiming at. That is my challenge with induction. I have taken a look at the link and I see that I have reached here $\sum_{m=0}^{n}\binom{n}{m}u^m (v^{n+1-m}) + \sum_{m=0}^{n}\binom{n}{m}(u^{m+1}) v^{n-m}$. But Cameron Buie lost me when he reindexed the sum. Like how does $m$ become $m-1$? I searched reindexing of summation but found nothing. Seeing the full solution to the end would be wlc – Parousia Apr 04 '17 at 06:36
  • plus any tips on induction would be welcome. I think I'm in that confusion bubble right now @dezdichado. sorry i'm asking too many questions. its how best i learn. – Parousia Apr 04 '17 at 06:38