Explore SharePoint 2016, the web-based, collaborative platform that integrates with Microsoft Office to provide intranets, secure document management, and collaboration so you can develop your online and offline capabilities.

Hey,

I had a question about simplifying a polynomial divided by a natural number... I start off with

((9^n) + 24n + 15)/48

And I have to show that this works for n+1 too... So I have...

((9^(n+1)) + 24n + 24 + 15)/48

Its the 9^(n+1) that's killing me... I've tried everything I could think of, but I couldn't get rid of it...

Appreciate any tips/pointers on this.

I had a question about simplifying a polynomial divided by a natural number... I start off with

((9^n) + 24n + 15)/48

And I have to show that this works for n+1 too... So I have...

((9^(n+1)) + 24n + 24 + 15)/48

Its the 9^(n+1) that's killing me... I've tried everything I could think of, but I couldn't get rid of it...

Appreciate any tips/pointers on this.

Do more with

EXPERT OFFICE^{®} is a registered trademark of EXPERTS EXCHANGE^{®}

what is the '

AW

can't be done, since the term 9^(n+1) = 9*9^n and that can't be shown as 9^n plus some numbers.

((9^(n+1)) + 24(n+1) + 15)/48 = (9^n + 24n + 15)/48 + (8*9^n + 24)/48

AW

Where did you get this, what does it mean, and what is it for?

This isn't a very complicated expression. You could evaluate using Excel for n = 1 ...

I've done that. It is interesting that all the answers are integers. Is that what you are talking about?

Also, once n is larger than 4 or so, the exponential term dominates. So each term is approx 9x its predecessor.

```
1 1.00
2 3.00
3 17.00
4 139.00
5 1233.00
6 11075.00
7 99649.00
8 896811.00
9 8071265.00
10 72641347.00
11 653772081.00
12 5883948683.00
13 52955538097.00
14 476599842819.00
15 4289398585313.00
16 38604587267755.00
17 347441285409729.00
```

First define your function

f(n) = 9^n + 24n + 15 (1)

and assume that there exists an integer k such that for some particular integer n, then

f(n) = 48 k (2)

Then, as you did in your OP, compute

f(n+1) = 9^(n+1) + 24(n+1) + 15

You want to show that if (1) is true, then

f(n+1) = 48 k2 for some integer k2 (3)

What you are trying to show is that if (2) is true, then (3) is also true. This is proof by induction.

http://en.wikipedia.org/wiki/Mathematical_induction

The base case is f(1) = 48

You have already computed

f(n+1) = 9^(n+1) + 24(n+1) + 15

Tip #1:

Now, using d-glitch formula in first post: 9^(n+1) = 9*9^n

f(n+1) = 9*9^n + 24(n+1) + 15 (4)

Tip #2:

Looking at (1) and (4), you can see a common expression, 9^n

Solve for 9^n in (1)

Tip #3:

When you do a few more steps, you will find a number of terms each having a factor of 48 in them. You can factor this 48 out and come up with the final desired result.

Of course it does.

But do you want the result to be an integer (or something else definite)?

And I have to show that this works for n+1 too... So I have...

((9^(n+1)) + 24n + 24 + 15)/48"

--

If you replace the first n by n+1 you must replace the second n by n+1 too.

f(n+1) = 9^(n+1) + 24(n+1) + 15

= 9^(n+1) + 24n + 24 +15

You want to show that there exists an Integer, k2, such that

f(n+1) = 48 k2

A/48 = m, an integer (i.e., no remainder)

So, obviously A = 48 m

If you work with the f(n) = 9^n + 24n + 15, and not divide by 48, you may find it easier (although either way should work).

8*9^n + 24 = 8*(9^n +3) so, is 9^n+3 always divisble by 6

that reduces to 8*9^n being divisible by 6 which is true (8*9^n = 4*2*(3^(2n))= 4*6*3^(2n-1) which IS divible by 6)

That proves the original hypothesis: (9^n+24n+15) is always divisible by 48

AW

((9^(n+1)) + 24(n+1) + 15)/48 = (9^n + 24n + 15)/48 + (8*9^n + 24)/48

so if (9^n + 24n + 15) is divisible by 48, and (8*9^n + 24) is also divisible by 48, then it follows that ((9^(n+1)) + 24(n+1) + 15) will be divisible by 48, which proves the original assertion.

AW

To see the 8 * 9^n, you can compute f(n+1) - f(n) and watch most of terms cancel out.

>> (8*9^n + 24) is also divisible by 48

This shows you that it would be useful for you to work out both approaches if you want to obtain more in-depth learning. Each approach has nice things to learn.

See if you can prove (without induction) that (8*9^n + 24) is also divisible by 48.

what is the problem with proving that WITH induction (which I demonstrated above is quite straight forward) ?

AW

```
If you are familiar with modular arithmetic:
9^1 = 9 ==> 9 mod 48 24*1 = 24 ==> 24 mod 48
9^2 = 81 ==> 33 mod 48 24*2 = 48 ==> 0 mod 48
9^3 = 729 ==> 9 mod 48 24*3 = 72 ==> 24 mod 48
9^4 = 6561 ==> 33 mod 48 24*4 = 96 ==> 0 mod 48
This pattern continues ...
For n = odd ==> 9 + 24 + 15 = 48
For n = even ==> 33 + 0 + 15 = 48
```

We have been showing multiple families of solutions. I offered another one since it is not obvious after looking at:

(9^n + 3) for a second or two that this expression is divisible by 2.

If the author goes through every approach, then there will be a nice bag of tricks for the future.

## Premium Content

You need an Expert Office subscription to comment.Start Free Trial